I'm not completely sure this is what you're looking for, but after playing a bit with the suggested inequality, I think I have found a combinatorial way of thinking about it. In fact, we shall prove the following inequality of which the inequality we are interested in is a special case (in fact, they are equivalent):
Inequality. Let $m,n\in\mathbb{N}$ and let $k_1,k_2,\cdots k_n\in\mathbb{N}$ (yes, this is the same $n$) be natural numbers such that $k_1+k_2+\cdots+k_n=mn$. Then the following inequality holds: $$m^n \geq k_1k_2\cdots k_n\qquad(*)$$
(Taking $m=x_1+x_2+\cdots+x_n$ and $k_i = nx_i$ yields the inequality in the question.)
We shall proceed by a constructiong a sequence of injections. The following lemma is easy to see. (It is basically just the combinatorial interpretation of the inequality $k l\leq (k+1)(l-1)$ which holds for natural numbers $k<l$.)
Lemma. Let $k,l\in\mathbb{N}$ be numbers such that $k<l$. Let $A,B$ be sets such that $|A|=k$ and $|B|=l$ and let $b\in B$. Then there is an injection $\phi:A\times B\to (A\cup\lbrace b\rbrace)\times(B\setminus\lbrace b\rbrace)$.
Proof. Since $k<l$, we have $k\leq l-1$, which means that there is an injection $\psi:A\to B\setminus\lbrace b\rbrace$, so we can define $\phi$ by $$\phi(x,y)=\begin{cases}(x,y);&\textrm{if }y\neq b,\\(b,\psi(x));&\textrm{if }y=b.\end{cases}$$ It is straightforward to verify that this is indeed an injection, so we are done.
From this lemma we get the following proposition, which is the inequality $(*)$ interpreted combinatorially.
Proposition. Let $m,n\in\mathbb{N}$ and let $A_1,A_2,\cdots,A_n$ be disjoint finite sets such that $\sum_{i=1}^n|A_n|=nm$. Let $B$ be a set such that $|B|=m$. Then there is an injection $\phi:A_1\times A_2\times\cdots\times A_n\to B^n$. ($B^n$ denotes $n$-tuples of elements from $B$, as usual.)
Proof. If $|A_i|=m$ for each $i$, there is not much to prove. Otherwise, there are indices $i_1$ and $i_2$ such that $|A_{i_1}|<m$ and $|A_{i_2}|>m$. Now choose some $c\in A_{i_2}$ and define a new partition of $\bigcup_{i=1}^n A_i$ as follows: $A_i^{(1)} = A_i$ for $i\neq i_1,i\neq i_2$ and $A_{i_2}^{(1)}=A_{i_2}\setminus\lbrace c\rbrace$, $A_{i_1}^{(1)}=A_{i_1}\cup\lbrace c\rbrace$. The above lemma allows us to construct an injection $\phi_1:A_1\times A_2\times\cdots\times A_n\to A_1^{(1)}\times A_2^{(1)}\times\cdots\times A_n^{(1)}$.
If now $|A_i^{(1)}|=m$ for each $i$, we are done, otherwise, repeat the same procedure, to obtain a partition $(A_{i}^{(2)})_i$ and an injection $\phi_2:A_1^{(1)}\times A_2^{(1)}\times\cdots\times A_n^{(1)}\to A_1^{(2)}\times A_2^{(2)}\times\cdots\times A_n^{(2)}$.
The procedure will terminate after finitely many steps, since at each step $j$ the sum $\sum_{i=1}^{n}|k_i^{(j)}-m|$ decreases so it will eventually reach zero at some step $r$. (Here we define $k_i^{(j)}=|A_i^{(j)}|$.) But this implies $k_i^{(r)} = m$ for each $i$, so $|A_i^{(r)}|=|B|$ for each $i$, so there is a bijection $\psi:A_1^{(r)}\times A_2^{(r)}\times\cdots\times A_n^{(r)}\to B^n$.
This means we have found a sequence of injections: $$A_1\times A_2\times\cdots\times A_n\overset{\phi_1}{\to}A_1^{(1)}\times A_2^{(1)}\times\cdots\times A_n^{(1)}\overset{\phi_2}{\to}\cdots\overset{\phi_r}{\to}A_1^{(r)}\times A_2^{(r)}\times\cdots\times A_n^{(r)}\overset{\psi}{\to}B^n$$ and the proof is complete.
Conclusion. We have constructed a sequence of injections that proves $(*)$, thus proving the A-G inequality in a combinatorial fashion. The combinatorial meaning of the proof is basically something like this: suppose we have a set $A$ and we partition it into $n$ non-empty parts. Then the number of ways to choose a single element from each set of the partition will be the greatest when the partition is into sets of equal size.
It’s not the best analogy, since it requires us to assume that we can actually choose which guests are vegan and which are vegetarian, but I’ll go ahead and use it.
We can first choose $m$ guests to be the vegetarians and vegans; this can be done in $\binom{n}m$ ways. Once they are chosen, we can pick some subset of them to be the vegans; this can be done in $2^m$ ways, since there are $2^m$ subsets of an $m$-element set. Thus, the righthand side does indeed count the ways to choose $m$ of the guests and split them into vegans and vegetarians.
Alternatively, we could first choose $k$ guests to be vegan, where $0\le k\le m$, and then we could choose $m-k$ of the remaining $n-k$ guests to be vegetarians. Thus, there are $\binom{n}k\binom{n-k}{m-k}$ ways to choose $k$ vegans and $m-k$ vegetarians. If we sum over all values of $k$ from $0$ through $m$, this gives us every possible way of choosing $m$ guests and splitting them into vegans and vegetarians, so the lefthand side counts the same thing as the righthand side.
Best Answer
Consider trying to count ordered triples $(x,y,z)$ of integers where
$0\le x< z$
$0\le y< z$
When $z=k$, there are $k$ choices for $x$ and $k$ choices for $y$, so the number of triples is indeed $\sum_{k=1}^nk^2$.
Alternatively, let us take all triples where $x<y$ and identify them with the subset $\{x,y,z\}$ of $\{0,1,2,\dots,n\}$. There are $\binom{n+1}3$ such subsets, each uniquely representing a triple where $x<y$.
The only remaining triples are the ones where $x\ge y$. Associate each such triple $(x,y,z)$ to the subset $\{y,x+1,z+1\}$ of $\{0,1,2,\dots,n+1\}$. There are $\binom{n+2}3 $ such subsets, each again uniquely representing a triple where $x\ge y$. The triple corresponding to $\{a<b<c\}$ is $(b-1,a,c-1)$.