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

<hr>

Added by André Henriques:<br>
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.