Edit: First version of this answer had a silly mistake (forgot to multiply by $n$ the first estimate). Argument is still the same but the final result changes.
If you take $n$ to be the product of the first $r$ odd primes, then the number of quadratic residues modulo $n$ is bounded below by ${(1/2)}^rn$, 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 a lower bound of $n^{1-c/\log \log n}$ for the number of quadratic residues. So you have a lower bound of the form $n^{1-\epsilon}$ for any $\epsilon>0$ if $n$ is large. I think the numbers I constructed will me minimal so you'll get your lower bound.
What did the drowning analytic number theorist say?