Your thoughts are, for the most part, correct, but you still get the wrong answer. That said your mistakes are perfectly understandable, so let's take a second to talk this through.
Recall that a group $G$ acts faithfully on a set of size $n$ if and only if $G$ is a subgroup of $S_n$, the symmetric group on $n$ letters. So secretly we're interested in the subgroups of $S_n$.
For $D_4$, you're completely correct that we get a faithful action on a set of size $4$ by permuting the vertices of a square. You're also correct that this is best possible. Indeed, $|S_3| = 6 < 8 = |D_4|$, so it's not possible for $D_4$ to be a subgroup of any symmetric group smaller than $S_4$. Thus here, $n=4$ works.
For $D_6$, you want to say that it has an element of order $6$, so can't embed in $S_n$ for $n < 6$. Since there's an obvious faithful action of $D_6$ on six points (permute the vertices of a regular hexagon), this should give the answer. But notice $|S_5| = 5! = 120$ is easily big enough to contain a $D_6$ (of size $12$) as a subgroup, and $S_5$ does have elements of order $6$ (indeed, $(1 \ 2 \ 3)(4 \ 5)$ is an example). So there's no obvious reason $S_5$ couldn't contain a $D_6$, and in fact it does! See here for a proof. The next obvious question is whether $S_4$ contains a copy of $D_6$. Since $|S_4| = 24$ this might still be possible, but now your idea comes to the rescue: $S_4$ has no elements of order $6$. See here for a proof. So now $n=5$ works.
Lastly, for $H$ the quaternion group, looking at the cycle structure is a good idea, but in fact here $n=8$ is the best we can do. Obviously $n=8$ works, since $H$ acts on itself by left multiplication. But it's kind of subtle to see why $n=7$ fails. See here for a proof (in the question) as well as a slick version of the same proof (in the answer).
As an aside, this question is quite hard in general, so you shouldn't feel bad for struggling with it. This $n$ is usually denoted $\mu(G)$ for a group $G$, and computing $\mu(G)$ for every finite group is still super unsolved! We know the answer when $G$ is abelian, and in other special cases too, but there's lots of work to be done. See here and here for more information.
As another aside, $\mu(D_n)$ is known too, and it can be much smaller than $n$. We already see this with $D_6$ embedding into $S_5$, but astonishingly $D_{360}$ is a subgroup of $S_{22}$! Even more spectacularly, $D_{9240}$ is a subgroup of $S_{34}$! In fact, as long as $n$ has many prime divisors, none of which is "too small", then $D_n$ embeds into an $S_m$ with $m \ll n$. See an old blog post of mine here for more details.
I hope this helps ^_^
