There are many group actions on sets which are linearly equivalent but not equivalent as actions. In fact, every group other than the cyclic group has one. This follows from some easy linear algebra:
- the number of irreducible reps over $\mathbb{Q}$ is the number of conjugacy classes of cyclic subgroups of $G$, (EDIT:there are at most this many since any two elements which generate conjugate cyclic groups have the same character in a rational representation; on the other hand, the characters of the inductions of the trivial from any set of cyclic groups, no two of which are conjugate, are linearly independent, so there are at least this many) and
- the number of non-isomorphic transitive G-sets is the number of conjugacy classes of subgroups.
Thus, there must be an integer valued linear combination of transitive actions which has trivial character. Moving all the actions with negative coefficients to the other side of the equality, we get two different actions with the same character, and thus isomorphic representations.
I actually wrote a paper about this a few years back, which I think is a reasonable starting place for the subject, which actually has quite a long history, and a reasonably extensive literature.
I believe the answer is that the class of an element of $g \in A_n$ becomes a single class when lifted to the 2-fold central covering group of $A_n$ if and only if $g$ has even order and $g$ has (at least) two cycles of the same length (including cycles of length 1).
The class of an element of $g \in S_n$ lifts to a single class in either of the two covering groups of $S_n$ if and only if either the condition for $g \in A_n$ holds, or $g$ has an even number of cycles of even length.
Let $\hat{S}$ and $\hat{A}$ be covering groups of $S_n$ and $A_n$. Let $z$ be the central element of order 2 in $\hat{S}$. To avoid too many hats, I will denote the inverse image in $\hat{S}$ of $g \in S_n$ also by $g$.
I believe that to study these covering groups, all you really need to know is that if $g$ and $h$ are disjoint transpositions in $S_n$, such as $(1,2)$ and $(3,4)$, then $[g,h] = z$ in $\hat{S}$. Also, for two commuting pairs of transpositions in $A_4$, like $g=(1,2)(3,4)$ and $h = (1,3)(2,4)$, we have $[g,h]=z$ in $\hat{A}$.
Clearly, if $g$ has odd order $k$ in $A_n$ or $S_n$, then its class lifts to two classes in $\hat{A}$ or $\hat{S}$, one of order $k$ and one of order $2k$, so we only need consider elements $g$ of even order.
If $g$ has two cycles of equal even length, such as $(1,2,3,4)(5,6,7,8)$ (+ other cycles) then we can take $h = (1,5)(2,6)(3,7)(4,8)$ and get $[g,h] = z$ in $\hat{A}$, so the class of $g$ lifts to a single class in $\hat{A}$. I had some difficulty proving that, but if it was false, then you could show that the centralizer of $h$ in $\hat{A}$ mapped on to the full centralizer of $h$ in $A_n$, which is not true, because the image of the centralizer does not contain $(1,2)(5,6)$.
On the other hand, if $g$ has even order and has two cycles of the same odd length, such as $g = (1,2)(3,4,5,6)(7,8,9)(10,11,12)$ with $n=12$, then we can take $h = (1,2)(7,10)(8,11)(9,12)$ and get $[g,h] = z$ in $\hat{A}$.
But if all cycles of $g$ have different lengths, then elements $h$ of the centralizer of $g$ in $A_n$ are made up of powers of those cycles, and since $h$ must have an even number of cycles of even length, we always get $[g,h]=1$ in $\hat{A}$.
However, in $S_n$, if $g$ has an even number of cycles of even length, like $g=(1,2)(3,4,5,6)$ with $n=6$, then we can take $h=(1,2)$ and get $[g,h]=z$ in $\hat{S}$.
Let me know if I have got something wrong, or if you would like more detail!.
Best Answer
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).