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 [result][1] that improves the bound of $\sqrt{p}$ to $\sqrt{p} - 1$ for infinitely many primes. 


  [1]: http://arxiv.org/abs/1305.0577