A trivial lower bound is $$p_{N,n,\gamma} \geq 1 - \binom{N}{2} \mathbb P ( d_H (x_1,x_2)< \gamma n) \geq  1 - \binom{N}{2}  ( \gamma^{-\gamma} (1-\gamma)^{-(1-\gamma) } 2^{-1} ) ^n $$ with the last inequality for $\gamma \leq 1/2$.

This in particular implies that $\lim_{n\to\infty} p_{2^{cn^\alpha}, n,\gamma}=1$ for all $\gamma < 1/2$ and $\alpha<1$, as well as for $\gamma<1/2, \alpha=1, c< ( (-\gamma \log \gamma - (1-\gamma) \log (1-\gamma) ) - \log 2 )/2$.