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.