Return to Revisions

I don't have a precise answer, but the genus of $S$ has to grow like $n!$.

To see this, note that when $n$ is large enough, $S$ cannot be the sphere or torus. So $S$ admits hyperbolic metrics. By Nielsen realisation (due to Kerckhoff) the surface $S$ admits a hyperbolic metric invariant under the $S_n$ action. The quotient is an orbifold. So it has area greater than or equal to the area of the $(2, 3, 7)$-triangle in the hyperbolic plane. That is, it has area at least $\pi/42$. So $S$ has area at least $n! \cdot \pi/42$. Since the area of $S$ equals $2\pi(2g - 2)$ we deduce that the genus is bounded below by a linear function of $n!$.

Added by André Henriques:
David Speyer and Nick Gill have shown, in the comments, that for $n$ large enough (specifically $𝑛\ge 167$), the symmetric group $𝑆_𝑛$ acts faithfully on a surface of genus $g$, with $𝑔−1=\frac{𝑛!}{168}$. As argued above, this is optimal.