Smallest example of a group that is not isomorphic to a cyclic group, a direct product of cyclic groups or a semi direct product of cyclic groups. 
What is the smallest example of a group that is not isomorphic to a cyclic group, a direct product of cyclic groups or a semi-direct product of cyclic groups?

So finite abelian groups are ruled out, as are the groups up to order $7$ I believe, since $1,2,3$ are all isomorphic to cyclic groups, $4$ has two non-isomorphic groups one cyclic and one isomorphic to the direct product $\Bbb{Z/2Z\times Z/2Z}$. $5,7$ are prime and so must be cyclic, and there's only one nonabelian group of order $6$ which is isomorphic to $\Bbb{Z/3Z\rtimes Z/2Z}$. Is it the quaternion group?

The quaternion group is indeed the minimal counter-example. Clearly, any group of orders $1,2,3,5$ or $7$ is cyclic, and the two (non-isomorphic) groups of order $4$ are:
$\Bbb Z_4$ and $\Bbb Z_2 \times \Bbb Z_2$.
There are likewise just two non-isomorphic groups of order $6$:
$\Bbb Z_6$ and $S_3 \cong \Bbb Z_3 \rtimes \Bbb Z_2$ (this is the only possible non-trivial semi-direct product of these two groups, since:
$0 \mapsto 1_{\Bbb Z_3}\\1 \mapsto (x \mapsto -x)$ 
is the sole non-trivial homomorphism $\Bbb Z_2 \to \text{Aut}(\Bbb Z_3)$).
It is convenient to use this formulation of a(n internal) semi-direct product:


*

*$G = NH$, where $N,H$ are subgroups of $G$, and $N \lhd G$.

*$N \cap H = \{e_G\}$.
The problem with obtaining $Q_8$ as a semi-direct product of two proper subgroups, is that we must have either $|H|$ or $|N|$ equal to $2$. But the only subgroup of order $2$ in $Q_8$ is $\{1,-1\}$, which is a subgroup of every subgroup of $Q_8$ of order $4$:
$\langle i\rangle = \{1,-1,i,-i\}\\\langle j\rangle = \{1,-1,j,-j\}\\\langle k\rangle = \{1,-1,k,-k\}$
Note that all $6$ elements of order $4$ lie in one of these $3$ subgroups.
Thus the condition $N \cap H = \{e_G\}$ (which is $=\{1\}$ in this case) is impossible to satisfy.
