Which finite groups have their minimal permutation degree equal to their order?
It might be worth producing a quick proof here, as the result is not difficult. (I came up with this, then checked Johnson's proof, which is incredibly similar.)
We proceed by induction on $|G|$, aiming to show that $G$ is $C_{p^n}$, $C_2\times C_2$, or $Q_{2^n}$.
If $G$ has two distinct subgroups $A$ and $B$ of prime orders $p$ and $q$ respectively (allowing $p=q$) then $G$ acts on the cosets of $A$ and $B$, yielding a faithful permutation representation on $|G|/|A|+|G|/|B|=|G|/p+|G|/q$ points. This is less than $|G|$ unless $p=q=2$. Thus we may assume that $G$ is a $p$-group with a unique subgroup of order $p$, or $p=2$. In the former case, it is a 'standard' fact that $p$-groups with a unique subgroup of order $p$ are cyclic or generalized quaternion. This yields the first and third of our options.
Thus by induction $p=2$, $G$ has two subgroups $A$ and $B$ of order $2$, and they are necessarily normal, else $G$ has a faithful representation on the cosets of $A$ (or $B$). The minimal degree of $G$ is at most the sum of that of $G/A$ and $G/B$, both of order $|G|/2$, so if $G$ is Cayley then both $G/A$ and $G/B$ are. If either is $C_2\times C_2$ then $|G|=8$ and we can just check, so both are cyclic or generalized quaternion. Thus $G/A$ has a unique subgroup of order $2$ for any subgroup $A$ of order $2$, so there is a unique subgroup of order $4$ containing $A$. Since there is more than one element of order $2$, there can therefore be no element of order $4$ squaring into $A$. But $A$ was chosen arbitrarily, so $G$ has no elements of order $4$ at all.
Thus $G$ has exponent $2$, so is abelian, and has a unique subgroup of order $4$ containing any given element of order $2$, so is $C_2\times C_2$, and we are done.
To make sure this does not go unanswered (but I'm making it community wiki):
As Derek Holt points out, a similar question was asked in math.overflow; that question asked more generally what is the minimal degree of a group.
An answer by Jack Schmidt there cites the paper:
Johnson, D. L. "Minimal permutation representations of finite groups." Amer. J. Math. 93 (1971), 857-866. MR 316540 DOI: 10.2307/2373739.
The paper is available on JSTOR (second link above). Theorem 1 states:
Theorem 1. The regular representation of a group $G$ is minimal if and only if $G$ is
- a cyclic group of prime power order, or
- a generalized quaternion $2$-group, or
- the [Klein] four-group.
So this says that your question about $Q_{16}$ has a positive answer, and that the ones you found are essentially (except for larger generalized quaternion groups) all the examples of what you've called Cayley groups.