The only proof I know that every faithful rep of \(S_n\) has dimension at least \(n - 1\) goes like this:

1. Write down the irreducible representations of \(S_n\).
2. Observe that you wrote a number of reps equal to the number of conjugacy classes and so conclude that you found them all.
3. Observe that the smallest dimensional faithful irrep has dimension \(n - 1\).
4. The non-faithful representations can only see the sign, and so don't help in building a faithful rep, thus every faithful rep contains a faithful irrep and so has dimension at least \(n - 1\).

Under some reasonable(?) complexity-theoretic assumption, we can give a really simple proof that any faithful rep has dimension \(\Omega(n^c)\) for some constant \(c > 0\). Is there a simple unconditional proof?