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) ) - 1 )/2$ (with the logarithms to base $2$).
I would guess that this value of $c$ is actually the transition point.