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!$.