There can be no method prettier than Henry's pairing argument. So let's work in the opposite direction, and look for an ugly argument.
When we go from $n$ to $n+1$, the factorial function grows by a factor of $n+1$. What about the other function? It grows by the factor
$$\frac{\sqrt{(n+1)^{n+1}}}{\sqrt{n^n}},$$
which simplifies to
$$(n+1)^{1/2}\left(1+\frac{1}{n}\right)^{n/2}.$$
Recall that $(1+1/n)^n<3$. So if $n+1>3$, the second function grows by a factor that is less than the growth factor of the factorial function. Now we hunt for a place >$2$ at which $n!>\sqrt{n^n}$. Beyond it, everything will be OK.
Another way: Next we look at estimates, in an attempt to carry our your other proposed argument. It is easier to work with logarithms. We want to show that if $n$ is large enough, then $\log(n!)>
\frac{1}{2}n\log n$.
Draw the curve $y=\log x$. Draw the rectangle with base $[1,2]$ and height $\log 2$, the rectangle with base $[2,3]$ and height $\log 3$, and so on up to the rectangle with base $[n-1,n]$ and height $\log n$. The sum of the areas of these rectangles is $\log 1+\log 2+\cdots+\log n$. By comparison with the area under the curve $y=\log x$ from $1$ to $n$, we conclude that
$$\log(n!) > \int_1^n \log x\,dx =n\log n -n +1.$$
(The integration is not hard, one does it by parts, letting $u=\log x$ and $dv=dx$.)
Now it is enough to show that $n\log n -n+1 >\frac{1}{2}n\log n$, or equivalently that $\frac{1}{2}n\log n -n+1>0$, if $n$ is large enough. Making sure that $\frac{1}{2}\log n >0$ will do the job, but we can do better because we get some help from the $1$.
The integral estimate we got for $\log(n!)$ can be refined quite a bit. After all the refinements are done, we obtain the Stirling approximation to $n!$, a result of great importance.