How powerful is Cayley's theorem?

So the Cayley's theorem gives a subgroup $H$ of $S_n$ for a $G$ such that $G$ is isomorphic to $H$. So $S_n$ behaves like a Universal set to $G.$

Is there a smaller universal object for all groups of size $n$?

It is probably worth noting that embeddings in symmetric groups of minimal degree have been studied by multiple authors, amongst them, D. L. Johnson, Minimal permutation representations of finite groups, Amer. J. Math. 93 (1971), 857-866, D. Wright, Degrees of minimal embeddings for some direct products, Amer. J. Math. 97 (1975), 897–903. See also N. Saunders, Minimal Faithful Permutation Degrees of Finite Groups, Aust. Math. Soc. Gazette 35, no.2 (2008), 332-338, and Strict inequalities for minimal degrees of direct products, Bull. Aust. Math. Soc. 79, no.1 (2009), 23–30 by the same author.

Further, and to be complete, I should mention the paper by David Easdown and Cheryl Praeger, On minimal faithful permutation representations of finite groups, Bull. Austral. Math. Soc. 38 (1988), 207-220, and a more "recent" paper that bears the same title, but was authored by L.G. Kovács and Cheryl Praeger, Bull. Austral. Math. Soc. 62 (2000), 311-317.

Finally, in Minimal embeddings of small finite groups (see https://arxiv.org/abs/1706.09286) Robert Heffernan, Des MacHale and Brendan McCann determine the groups of minimal order in which all groups of order $n$ can embedded for $1 \leq n \leq 15$. They further determine the order of a minimal group in which all groups or order $n$ or less can be embedded, also for $1 \leq n \leq 15$.

One nice result is the following: Let $G$ be a group of minimal order in which all groups of order $12$ can be embedded. Then $G \cong S_3 \times S_4$.

The answer is 'sometimes'. For example, all groups of order $6$ ($C_6$ and $S_3$) lie in $S_5$, but the quaternion group $Q_8$ of order $8$ requires $S_8$. There are infinitely many $n$ such that there is a group of order $n$ that does not embed in $S_{n-1}$, and infinitely many for which this is not true.

Edit: More easily, cyclic groups of order $p^n$ cannot embed in $S_{p^n-1}$.

But if $n$ is not a prime power then all groups of order $n$ do embed in $S_{n-1}$. To see this, since $G$ does not have order a prime power it is divisible by two primes $p$ and $q$. Then $G$ has an element of order $p$ and an element of order $q$, $x$ and $y$ say. The action on the cosets of $\langle x\rangle$ union the action on the cosets of $\langle y\rangle$ yields a (faithful!) embedding of $G$ into a symmetric group of degree $|G|/p+|G|/q<|G|$.

Edit 2: If one just wants a proper subgroup of $S_n$ containing all groups of order $n$, then this is always the case for all $n>2$. The only cases that need to be dealt with are $n$ a prime power, as above. But then all $p$-groups are contained in a Sylow $p$-subgroup, which has order the $p$-part of $n!$. This is (obviously) much smaller than $n!$.

In general, I (although Nicky Hekster apparently has) have never seen any work on constructing a minimal group containing all groups of order $n$. For $n=6$, for example, this group is the dihedral group $D_{12}$, which is $C_2\times S_3$. This is much smaller than $S_5$, the smallest symmetric group containing both groups of order $6$. If $|G|=p^2$ then this is $C_{p^2}\times C_p$, of order $p^3$.

As a first example of such a "smaller universe", think of any finite $G$ having a proper normal subgroup, $H$. Then, $G$ acts by conjugation on $H$, and the kernel of this action is $C_G(H)$. Therefore, if $C_G(H)$ is trivial, then $G$ embeds into $S_{|H|}$, which is a "smaller universe" than (Cayley's) $S_{|G|}$. For instance, $C_{S_4}(A_4)=\{1\}$ and hence $S_4\hookrightarrow S_{12}$ (with no claim that this is the minimal embedding).

On the contrary, if $|G| = p > m$ is prime, then $p \not\mid |S_m| = m!$. Therefore there cannot be an embedding $G \hookrightarrow S_m$, because its image would be a subgroup of order $p$, contradicting Lagrange's theorem. So, in this case, Cayley's one is the "smallest possible universe".