I recommending listing all the possibilities. A number of sources already do this, so it is fairly easy to do again; the table in the ATLAS is quite reasonable. Basically, the outer automorphism group is ridiculously small "most" of the time, so you might care about the details.
I think you'll get |Out(G)| ≤ C*log(|G|) as worst case, but this is pretty pessimistic most of the time.
The outer automorphism group of an alternating group has order at most 4, and almost always has order 2. There are finitely many sporadic groups, and so will not matter asymptotically, but you can quickly check over the list to see they have outs of size at most 2.
The groups of Lie type have a 3-part outer-automorphism group; the diagonal, the field, and the diagram parts. The diagram part has order at most 6 (and only for D4). The field part is cyclic, but can be "large", as in, if "q" of your group is p^f, then it is cyclic of order f. The diagonal part is usually small (order at most 4, or even order at most 2), but can be larger for PSL(n,q) and PSU(n,q). Even there it is cyclic of order at most n.
So basically you handle the case of PSL/PSU a little more carefully, then the case of a general group of Lie type using bounds of 4 and 6 for diagonal and diagram so getting something like O(log(|G|)), then you handle the rest which are bounded by a constant.