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?

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 be minimal so you'll get your lower bound.

What did the drowning analytic number theorist say?

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?

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?