classification of small complete groups This is "escalated" from stackexchange. 
So, $S_n$ for $n \ne 2,6$, $\text{Aut}(G)$ for $G$ non-cyclic simple, $\text{Hol}(C_p)$ for $p$ odd prime are well-known classes of complete group. 
What's the smallest complete group not in these classes? What's a possible way to generalise that group, and what's the smallest complete group not in that class either? And so on. I'd be interested in any partial result.
 A: Here's an infinite family of complete groups. Let U be cyclic of prime order p > 2 should  and let G be the holomorph of U, so U is normal in G (and in fact is characteristic) and G/U is cyclic of order p-1. It is easy to see that Z(G) = 1. Also U is complemented in G and there are exactly p complements, and they are all conjugate in U. Further, no nonidentity element of G normalizes all of the complements of U in G.
Embed G as a normal subgroup of A = Aut(G). I argue that A = G. Now A permutes the set of complements for U in G via conjugation. If N is the kernel of this action, then N is normal in A. Also, N meet G is trivial by the last sentence of the previous paragraph. It follows that N centralizes G, but since A = Aut(G), we see that N = 1.
Thus A acts faithfully on the set of p complements for U in G, and thus A is isomorphically embedded in the symmetric group S_p. But U is normal in A and U has order p. Since the full normalizer of a cyclic group of order p in S_p has order p(p-1) = |G|, it follows that |A| <= |G| so A = G, and thus G is complete.

It should be mentioned in this context that if G is any finite group with trivial center, then G embeds in Aut(G) and Aut(G) has trivial center, so this process can be repeated, yielding an "automorphism tower" G <= Aut(G) <= Aut(Aut(G)) <= ... . A marvelous theorem of Wielandt shows that this process eventually terminates in a complete group. (For a proof, see my group theory text.)
A: Here's a very partial "experimental" result, using some GAP computations and the library of small groups in GAP. I am afraid this does not provide any deep theoretical insight, but it might at least give some ideas and starting points.
There is not really an efficient way to check whether a group is complete,  I think; however, one thing is sure: It can't be nilpotent (as nilpotent groups have non-trivial center). The small groups library knows for every group in it whether it is nilpotent, so we can filter those out. There are 1048 groups of order 1 to 100; of these 464 are not nilpotent, as the fol.owing code verifies:
gap> Sum(List([1..100],NumberSmallGroups));
1048
gap> grps:=AllSmallGroups([1..100], IsNilpotentGroup, false);;              
gap> Length(grps);
464

Computing the center of a group is also relatively efficient, so let's remove all with non-trivial center:
gap> grps:=Filtered(grps,g->IsTrivial(Center(g)));;
gap> Length(grps);
72

Finally, the condition on the automorphism group:
gap> grps:=Filtered(grps,g->Size(g)=Size(AutomorphismGroup(g)));;
gap> Length(grps);
5

So what are these groups? If we just print "grps", we don't see much, but we can ask GAP to try to come up with "nice" labels for the groups (they just give a rough idea of the group's structure; they are not enough to recover the group):
gap> List(grps, StructureDescription);
[ "S3", "C5 : C4", "S4", "(C7 : C3) : C2", "(C9 : C3) : C2" ]

Note that GAP denotes semidirect products by "N : H", where N is normal. Also note that in general there are many ways to write a group as, say, a semidirect product, and GAP may not pick the most "natural" one -- after all what is "natural" is highly subjective.
Anyway, so we get $S_3$, $S_4$ and the holomorphs of the cyclic groups of order 5, 7 and 9. The last one is not in your list (but almost)... Continuing with a slightly more elaborate program (looping over the orders instead of grabbing all groups of a lot of orders at once, as that will easily overflow memory), we find 27 complete groups up to and including order 500:


*

*$S_3$

*$Hol(C_5)$

*$S_4 \cong Hol(C_2^2)$

*$Hol(C_7)$

*$Hol(C_9)$

*$Hol(C_{11})$

*$S_5$

*$S_3 \times Hol(C_5)$

*$((C_3^2) : C_8) : C_2$

*$S_3 \times S_4$

*$Hol(C_{13})$

*$((C_2^3) : C_7) : C_3 < Hol(C_2^3)$

*$(((C_2^2) : C_9) : C_3) : C_2$

*$S_3 \times Hol(C_7)$

*$Hol(C_{17})$

*$((C_2^4) : C_5) : C_4$

*$S_3 \times Hol(C_9)$

*$PSL(3,2) : C_2$

*$Hol(C_{19})$

*$((((C_4^2) : C_3) : C_2) : C_2) : C_2$

*$((((C_2^4) : C_3) : C_2) : C_2) : C_2$

*$(((C_3^2) : C_3) : Q_8) : C_2$

*$(((C_6^2) : C_3) : C_2) : C_2$

*$(((C_3^2) : Q_8) : C_3) : C_2 \cong Hol(C_3^3)$

*$Hol(C_5) \times S_4$

*$Hol(C_{27})$

*$Hol(C_{25})$ (order 500)


So, besides the classes you named, we also get holomorphs of cyclic groups of prime-power order; direct products of complete groups, plus some other groups which one should study a bit closer to understand.
