OK, thinking a little more clearly about this... (hopefully) Say $p \in (N,2N]$ fails to have the property you want. Then $p | n^r-1$ for some $|n| < \sqrt{p} \le \sqrt{2N}$. There are only $O(\sqrt{N})$ integers of the form $n^r-1$ with $n$ in this range, and each has only $O(\log{N})$ prime factors. So there are only $O(\sqrt{N} \log{N})$ exceptional primes in this interval. Replacing $N$ with $N/2, N/4$, etc., we see that the total number of exceptional primes up to $N$ is also $O(\sqrt{N}\log{N})$, which is tiny compared to $\pi(N)$.

OK, thinking a little more clearly about this... (hopefully) Say $p\le N$ fails to have the property you want. Then $p | n^r-1$ for some $|n| < \sqrt{p} \le \sqrt{N}$. There are only $O(\sqrt{N})$ integers of the form $n^r-1$ with $n$ in this range, and each has only $O(\log{N})$ prime factors. So there are only $O(\sqrt{N} \log{N})$ exceptional primes $p \leq N$, which is tiny compared to $\pi(N)$.