This is a little late, but since this is the first thing that pops up with a google search of cliques in Paley graphs, I will mention the following: here is a resultresult that improves the bound of $\sqrt{p}$ to $\sqrt{p} - 1$ for infinitely many primes.
Ben Barber
- 4.6k
- 2
- 25
- 38