I don't know how to answer your question, but I'll suggest a possible approach, i.e. a source of examples that potentially have large girth.
As I'm sure you're aware, Margulis constructed graphs of large girth which were Cayley graphs of $SL_2(\mathbb{Z}/p)$. The point is that reducing a free subgroup $SL_2(\mathbb{Z}) (\mod p)$, one could show that words in the generators must have a certain length before they could be trivial by computing the operator norm of products of matrices.
These graphs achieve the optimal growth of girth of $O(\log(n))$, where $n$ is the number of vertices. His approach works for families of simple groups of Lie type, by reducing linear representations $(\mod p)$.
By analogy, one could hope to achieve Cayley graphs for the symmetric or alterating groups by considering non-linear actions of free groups on varieties, and reducing $(\mod p)$ to get families of finite actions.
Recently Bourgain, Gamburd, and Sarnak have investigated such actions for the Markoff equation:
$$ x^2+y^2+z^2=xyz.$$
The automorphism $\theta: (x,y,z)\mapsto (y,z, yz-x)$ (found by exchanging the two solutions of the quadratic formula in the variable $z$ and permuting) together with permutations generates a virtually free group of automorphisms (in fact, it has a finite-index 2-generators subgroup). These act transitively on the fundamental solution $(3,3,3)$, giving the Markoff triples.
Subsequently it was shown by Meiri and Puder that the action on the solutions to the Markoff equation $(\mod p)$ is usually symmetric or alternating (the number of solutions is $O(p^2)$, so one gets generators for $Sym(O(p^2))$). Thus, one may ask for the girth of the Cayley graph associated to this action. It seems tricky to implement Margulis' method here, because it is not as easy to identify when a polynomial automorphism is trivial $(\mod p)$, unlike the linear case. Also, the growth of the action on the Markoff numbers is superexponential instead of exponential. One may show that on a ball of radius $c\log\log p$, the fundamental solution $(3,3,3)$ is not sent to itself. In particular, the orbit of $(3,3,3) (\mod p)$ under the element $\theta$ has size at least $\log\log p$. This is far off from optimal of course. But there is a bit of evidence that one can do much better: in this paper, it is shown that $\theta$ has a cycle of size $O(\log p)$. Moreover, Bourgain-Gamburd-Sarnak remark that experiments indicate that the Cayley graphs form an expander family, although they don't explicitly conjecture this or discuss the girth.
A heuristic that the girth should be at least $O(\log(p))$: taking the involution generators for the automorphism group $(x,y,z)\mapsto (x,y,xy-z), (x,xz-y,z), (yz-x,y,z)$, one sees that their compositions have degrees which grow at most exponentially (in fact, at most the Fibonacci sequence) with $n$ compositions. Since a non-trivial polynomial in $\mathbb{F}_p[x,y,z]$ must be non-vanishing if the degree of each variable is $<p$, we see that these polynomials will be non-identity if $n < c\log p$. Hence, one would expect that the girth is at least $O(\log p)$. The problem with this approach is that one should actually work over the ring of functions on the variety $\{ (x,y,z)\in \mathbb{F}_p^3 | x^2+y^2+z^2=xyz\}$, so one must make sure that the polynomials are not trivial in this ring. This is still far off from the "Girth of random graphs" result that you cite.
