What is the smallest $n$ such that the quaternion group is a subgroup of $S_n$?
Equivalently, we want to know the smallest $n$ such that $G = Q_8$ acts faithfully on a set of size $n$. Any action $X$ of $G$ decomposes as a disjoint union of transitive actions
$$X \cong \sum_i G/H_i.$$
Now, $G$ has the strange property that all of its subgroups are normal, so the kernel of the action of $G$ on $G/H$ is $H$. The action of $G$ on $X$ therefore has kernel $\cap_i H_i$, so the game here is to find subgroups of $G$ whose intersection is trivial such that the sum of their indices in $G$ is minimal.
$G$ has another strange property, which is that all of its nontrivial subgroups contain its center $\pm 1$. Hence the intersection $\cap_i H_i$ can't be trivial unless some $H_i = 1$. This gives $n = 8$.