There was this question for which my response was unusally popular, so I dare to ask the following:
(1) Given a prime $p>2$, how many primes $\ell < p$ there exist which are quadratic residues mod $p$?
(2) Given a prime $p>2$, how many primes $\ell < p$ there exist which are quadratic nonresidues mod $p$?
As for (1) I can prove $\gg\log p/\log\log p$ by an elementary argument. Indeed, put $p':=(-1)^{(p-1)/2}p$ and observe, by quadratic reciprocity, that a prime $\ell\neq p$ divides some value $x^2-p'$ for $x\in\mathbb{Z}$ if and only if $\ell$ is a quadratic residue mod $p$. Now consider $|x^2-p'|$ for $0 < x < \sqrt{p}$: these are integers in $(0,p)$ or $(p,2p)$ depending on $p$ mod $4$. At any rate, these numbers are built up from the $k$ primes enumerated under (1), and their number is $\gg\sqrt{p}$. As each of the $k$ prime exponents is $\ll\log p$, we conclude $\sqrt{p}\ll(\log p)^k$ and my claim follows.
Added 1. As Anonymous pointed out, we should restrict to odd $0 < x < \sqrt{p}$, and talk about the odd part of $|x^2-p'|$. In addition, using the upper bound part of (7.16) on p. 203 of Montgomery-Vaughan: Multiplicative Number Theory (proof on pp. 204-208), we can see $k>(\log p)^{2-o(1)}$ for the number of primes under (1).
Added 2. Regarding (2), Lucia pointed out that $\gg p^\delta$ follows with a decent $\delta>0$ from a result of Bourgain and Lindenstrauss. I found this response very satisfactory, and I accepted it officially. Still, I would welcome any further developments regarding the above questions (1) and (2).
Added 3. The recent preprint of Paul Pollack contains several nice new results and valuable historic references regarding the above two questions. An even more recent preprint by him and Kübra Benli settles (1) in the sense that there are $\gg p^{1/9}$ prime quadratic residues $\ell<p$.
Best Answer
GH from MO and Anonymous have commented above on (modest) lower bounds for the first problem. Let me mention here that a version of problem 2 (of producing many non-residues) appeared in work of Bourgain and Lindenstrauss in connection with the QUE conjecture. In particular, from Theorem 5.1 of their paper it follows that there is a positive constant $\delta$ such that at least $p^{\delta}$ of the primes $\ell$ below $p$ are quadratic non-residues $\pmod p$. The proof is based on the fundamental lemma of sieve theory together with cancelation in character sums.
Added: To elaborate, Theorem 5.1 of Bourgain and Lindenstrauss's paper shows that if $N=p^{\beta}$ with $\beta \ge 1/4+\epsilon$ then there exists $\alpha>0$ such that ($\ell$ runs over primes below) $$ \sum_{N^{\alpha} <\ell < N; (\frac{\ell}{p}) = -1} \frac{1}{\ell} \ge \frac 12 -\epsilon. $$ In particular the number of primes $\ell$ with $(\frac{\ell}{p}) =-1$ is trivially at least $(1/2-\epsilon)N^{\alpha}$. Now use this with $N=p$, and we deduce the result mentioned above. I didn't check the details, but I think one can get a pretty decent value of $\delta$ above -- maybe even as big as $3/8$ (the level of distribution is like $p^{\frac 34}$ and the sifting limit should be $1/2$).