If you take $n$ to be the product of the first $r$ odd primes, then the number of quadratic residues modulo $n$ is bounded above by ${(2/3)}^r$, by the Chinese remainder thm. On the other hand, $n$ is about $(1/2)e^{r\log r}$ by the prime number theorem, so you get an upper bound of $n^{c/\log \log n}$ for the number of quadratic residues. So you can't have a lower bound of the form $n^{\epsilon}$ for any $\epsilon$. I think the numbers I constructed will me minimal so if you carefully estimate the answer for those, you'll get your lower bound.

What did the drowning analytic number theorist say?