Let $r_2(n)$ be the sum of squares function, i.e. the number of different pairs $a,b\in \mathbb{Z}$ such that $a^2 + b^2 = n$. Let $R$ be the set of representable integers, i.e. the subset of $\mathbb{N}$ such that $r_2(n) > 0$.
I would like to know whether or not the following is true:
Fix $0 < \epsilon < 1/2$. Given large $x$, almost all $n \le x$ in $R$ satisfy $r_2(n) \ge (\log x)^{1/2 - \epsilon}$.
If this is hard/wrong, then I would also be happy with the following much weaker fact:
There is a function $f(x)$ that goes to $\infty$ when $x \to \infty$ such that almost all $n \le x$ in $R$ satisfy $r_2(n) \ge f(x)$.
Explanation for the "almost all":
Landau's theorem says the amount of $n \in R$, $n \le x$ is asymptotically $\displaystyle \frac {bx}{\sqrt {\log x}}$ where $b$ is Landau's constant.
So, I would like to know whether the number of exceptions to $r_2(n) \ge (\log x)^{1/2 - \epsilon}$ for $n\in R, n\le x$ is asymptotically negligible, i.e. $\displaystyle o\left(\frac x {\sqrt \log x}\right)$.
My thoughts on the problem:
By Gauss's solution of the circle problem we know that $\displaystyle \sum_{n\le x} r_2(n) \sim \pi x$. From this and Landau's theorem we know that the average value of $r_2(n)$ for $n \le x$, $n \in R$ is $\frac \pi b \sqrt {\log x}$. So this is the average value of $r_2(n)$ on $R, n\le x$.
By applying a sort of "Markov's inequality" we get the reverse direction of what I want: Let $E(x)$ by the number of exceptions, i.e. the number of $n \le x$, $n \in R$ such that $r_2(n) > (\log x)^{1/2 + \epsilon}$. Then $$\pi x \sim \sum_{n \le x} r_2(n) \ge E(x) (\log x)^{1/2 + \epsilon}$$ This means $$E(x) = o\left(\frac x {\sqrt {\log x}}\right)$$ meaning that almost all $n \le x$, $n \in R$ satisfy $r_2(n) \le (\log x)^{1/2 + \epsilon}$.
For the direction I'm interested this approach is not enough and we need a sort of "Chebyshev inequality". This means we want a sort of "second moment" of $r_2(n)$. I found it in this Math.StackExchange question: $\sum_{n \le x} r_2(n)^2 \sim ax \log x$ where $a$ is a constant. Unfortunately, this asymptotic is too poor, and when trying to use the above method on $\left|r_2(n) - \frac \pi b \sqrt{\log x}\right|$, the error term squashes the main term and we get nothing.
I thought about this some more, and I think the actual typical order of $r_2(n)$ should be $(\log n)^{\log 2/2}$. I don't have a full proof, but let me explain my thinking. Note that all $\log$'s in this answer are base $e$.
It is easier to first consider the number of ways to write $n = a^2+b^2$ with $a$ and $b$ relatively prime. Let $q_0(n)$ be the number of such ways to write $n$, let $R_0$ be the set of $n$ which can be written in this manner. Let $R_0(x)$ be $\{ n \in R_0: \ n \leq x \}$ and let $\rho_0(x) = \#R_0(x)$.
Recall that $n$ is in $R_0$ if and only if $n$ is of the form $2^{(0 \ \mathrm{or}\ 1)} p_1^{a_1} \cdots p_k^{a_k}$ where all the $p_i$ are $1 \bmod 4$. For $n$ of this form, $q_0(n) = 4 \cdot 2^{k}$. We will write $k$ as $k(n)$ when necessary to emphasize that it is a function of $n$.
It seems very likely to me that for almost all $n \in R_0$ with $n \leq x$, we have $k(n) \approx (1/2) \log \log x$. More precisely, I imagine that for $\epsilon>0$, the proportion of $n \in R_0(x)$ with $\frac{1-\epsilon}{2} \log \log x < k(n) < \frac{1+\epsilon}{2} \log \log x$ approaches $1$; I'll give heuristic arguments for this below. Assuming this, for almost all $n \in R_0$ with $n \leq x$ we have $$4 \cdot 2^{(1-\epsilon)/2 \log \log x} < q_0(n) < 4 \cdot 2^{(1+\epsilon)/2 \log \log x} .$$ But $$2^{(1/2) \log \log x} = (\log x)^{\log 2/2},$$ not $\sqrt{\log x}$.
Now, what happens when we work with all sums of squares, not just relatively prime ones? The details are messier, but I claim the conclusion is the same. We will use $q(n)$ for the number of ways to write $n$ as a sum of squares, $R$ for the set of $n$ which can be written as a sum of squares, $R(x)$ for $\{ n \in R :\ n \leq x \}$ and $\rho(x)$ for $\# R(X)$.
First of all, it should be easy to show that a positive proportion of $R$ is made up of square free integers. (The proportion should be $$\frac{3}{4} \prod_{p \equiv 1 \bmod 4} \left( 1- \frac{1}{p^2} \right) \prod_{p \equiv 3 \bmod 4} \left( 1- \frac{1}{p^2-p+1} \right),$$ because being in $R$ already constrains $n$ to one of $p^2-p+1$ residue classes modulo $p^2$ when $p \equiv 3 \bmod 4$.) For such elements $n$ of $R$, we have $q_0(n) = q(n)$. So that should already give a positive proportion of $R$ where $q(n)$ behaves like $(\log n)^{\log 2/2}$.
However, I claim that the situation is actually much stronger. Motivated by the above, let $\bar{R}$ be the squarefree elements of $R$. Note that $R = \bigcup_d d^2 \bar{R}$ and $q(n) = \sum_{d^2 | n} q_0(n/d^2)$. Fix a very large integer $D$ and set $R_D = \bigcup_{d \leq D} d^2 \bar{R}$. As $D \to \infty$, the proportion of $R$ which is occupied by $R_D$ should approach $1$. However, for $n \in R_D$, we have $q(n) = \sum_{\substack{d \leq D \\ d^2 | n}} q_0(n/d^2)$. So $q(n)$ should be at most $D (\log n)^{\log 2/2}$. This suggests that we should be able to show, for any $\epsilon$, that all but an $\epsilon$ proportion of the $n$ in $R(x)$ obey $q(n) < (\log n)^{\log2/2 +\epsilon}$.
So, why do I think that $k(n)$ is typically $(1/2) \log \log x$ for $n \in R(x)$ (or in $R_0(x)$)? First of all, it is the correct average value. $$\sum_{n \in R(x)} k(n) = \sum_{n \in R(x)} \sum_{\substack{p \equiv 1 \bmod 4 \\ p|n}} 1 = \sum_{p \equiv 1 \bmod 4} \rho(x/p).$$ Landau gives $\rho(x) \approx K x/\sqrt{\log x}$, so $\rho(x/p) \approx K (x/p)/\sqrt{\log x}$. (The symbol $\approx$ has no precise meaning; I leave working out the exact error term to you.) So $$\sum_{p \equiv 1 \bmod 4} \rho(x/p) \approx \sum_{\substack{p \equiv 1 \bmod 4 \\ p \leq x}} K \frac{x}{p \sqrt{\log x}} = \frac{K x}{\sqrt{\log x}} \sum_{\substack{p \equiv 1 \bmod 4 \\ p \leq x}} \frac{1}{p} \approx \rho(x) \frac{\log \log x}{2}.$$ Here are we using something like "Merten's theorem in arithmetic progressions". So the average value of $k(n)$ in $R(x)$ should be $\approx (\log \log x)/2$. (I am not claiming an actual proof, because of the issues lurking in interpreting $\approx$.)
Moreover, the same sort of argument suggests that the average value of $k(n)^a$ should be $\left( \frac{\log \log x}{2} \right)^a$.
Finally, Lucia at MO shows (non-uniformly in $k$) that the number of $n$ in $R_0(x)$ with $k(n)=k$ is $$\sim \frac{x (\log \log x)^{k-1}}{2^{k-1} (k-1)! \log x }.$$ This is a Poisson distribution, peaked at $(\log \log x)/2$.