Orbit structures of conjugacy class set and irreducible representation set under automorphism group let G be a finite group. Suppose C is the set of conjugacy classes of G and R is the set of (equivalence classes of) irreducible representations of G over the complex numbers.
The automorphism group of G has a natural action on C and also on R (we can make both of these left actions). My questions:

*

*Under what conditions are C and R equivalent as $\operatorname{Aut}(G)$-sets? This is definitely true, for instance, if every automorphism is inner, if the outer automorphism group of G is cyclic (it then follows from Brauer's permutation lemma) and it is also true if the quotient of the automorphism group by the group of class-preserving automorphisms is cyclic (again by Brauer's permutation lemma). But it also seems to be true in a number of other cases, such as the quaternion group, where the outer automorphism group is a symmetric group of degree three.

*A weaker condition: under what conditions are the orbit sizes under $\operatorname{Aut}(G)$ for C and R the same?

 A: I think that an example of non-equivalent permutation sets is given by
$G=(\mathbb Z/p\mathbb Z)^n$ for $n>2$ (and $p$ a prime). Then the automorphism
group is $\mathrm{GL}_n(\mathbb Z/p\mathbb Z)$, the conjugacy classes are in
natural bijection with $G$ and the set of irreducible representations are in
bijection with the dual group (or dual $\mathbb Z/p\mathbb Z$-vector space). In
both cases there are only two orbits, one of length $1$ (the identity element
and the trivial representation respectively). The stabilisers for elements in
the non-trivial orbits are not conjugate: Mapping to $\mathrm{PGL}_n(\mathbb
Z/p\mathbb Z)$ map these two kinds of stabilisers two non-conjugate parabolic
subgroups (stabilisers of lines resp. of hyperplanes).
A: By Brauer's permutation lemma, the permutation characters are always equal, but the representations need not be isomorphic.  For instance, the non-abelian group of order 27 and exponent 9 provides an example.  One condition for an equivalence for subgroups of the automorphism group is given in Isaacs's Character Theory textbook as theorem 13.24 on page 230–231:

If S is a solvable subgroup of Aut(G), and gcd(|S|,|G|)=1, then the permutation representations of S on Irr(G) and Cl(G) are isomorphic.

This will rarely directly answer your question as Aut(G) and G usually have common prime divisors, but perhaps the ideas will be useful to you.  In particular, it describes a strengthening of your #2 which implies #1.
Let me know if you would like GAP code to verify the order 27 example.  The action on classes has orbits of sizes 1, 1, 1, 2, 6 and the action on the irreducibles has orbits of sizes 1, 2, 2, 3, 3.
GAP code to check permutation isomorphism:
OnCharactersByGroupAutomorphism := function( pnt, act )
  return Character( UnderlyingCharacterTable( pnt ),
  pnt{FusionConjugacyClasses(act^-1)} );
end;;
OnCBGA := OnCharactersByGroupAutomorphism;;

g := ExtraspecialGroup(27,9);;
a := AutomorphismGroup(g);;
gensIrr := List( GeneratorsOfGroup(a), f ->
  PermListList( Irr(g), List( Irr(g), chi -> OnCBGA( chi, f ) ) ) );
gensCcl := List( GeneratorsOfGroup(a), f ->
  PermList( FusionConjugacyClasses(f) ) );
# perm iso?
fail <> RepresentativeAction( SymmetricGroup( NrConjugacyClasses( g ) ),
  gensCcl, gensIrr, OnTuples );

Some of what you asked for might be more along the lines of asking if the permutation groups generated by gensIrr and gensCcl are conjugate, so I chose an example where even the images are not conjugate.  The example given below of G=2×2×2 is the smallest if you only want strict permutation (non-)isomorphism.
