The statement you make about tetrahedra generalizes to arbitrary $n$. Specifically, the symmetric group $S_n$ is the group of symmetries of a regular $n$-simplex, and the alternating group $A_n$ acts on this simplex by rotations. (In fact, $A_n$ is precisely the set of rotational symmetries.) Elements of different conjugacy classes of $A_n$ are geometrically distinguishable, in the sense that they would "look different" to an observer in $\mathbb{R}^n$.
One way of making the notion of "look different" precise is that non-conjugate elements of $A_n$ correspond to non-conjugate elements of the rotation group $SO(n)$. Thus, two non-conjugate elements of $A_n$ do not look the same up to rotation of the simplex.
Incidentally, the simplest algorithm to distinguish conjugacy classes in $A_n$ is essentially to check the sign of the conjugator. For example, the elements $(5)(2\;6\;3)(1\;9\;4\;8\;7)$ and $(2)(1\;4\;8)(3\;7\;5\;6\;9)$ are conjugate in $S_9$, and their conjugacy class in $S_9$ splits into two conjugacy classes in $A_9$. To check whether the two elements are conjugate in $A_9$, we consider a permutation that maps between corresponding numbers:
$$
\begin{bmatrix}
5 & 2 & 6 & 3 & 1 & 9 & 4 & 8 & 7\\
2 & 1 & 4 & 8 & 3 & 7 & 5 & 6 & 9
\end{bmatrix} \;=\; (1\;3\;8\;6\;4\;5\;2)(7\;9)
$$
This permutation is odd, so the two elements are not in the same conjugacy class in $A_9$. It is possible to construe this algorithm geometrically, since the difference between odd and even permutations is the same as the difference between right-handed and left-handed coordinate systems.
You are correct that conjugacy in $S_n$ is equivalent to sharing a cycle structure.
You are also correct that, via Cayley's theorem, this implies that conjugate elements in any group do have the same cycle structure for the translation action of $G$ on itself.
Aside: The (left-)translation action of $G$ on itself is the action that, for a given element $g$ of $G$, sends any element $h$ of $G$ to $gh$. The name "translation" is by analogy with the fact that when the Euclidean plane, seen as the vector space $\mathbb{R}^2$, acts on itself this way, each group element acts as a plane translation. In general, the translation action shares with plane translations the property that everybody moves, i.e. if $g\in G$ is not the identity, then $gh$ never equals $h$, so $g$'s action on $G$ causes every point to move somewhere else.
The identification in Cayley's theorem of a subgroup of $S_n$ isomorphic to $G$ is usually based on this action: one maps $g\in G$ to the permutation in $S_{|G|}$ describing the action of $g$ on $G$ by translation, and then proves that this map is a group isomorophism onto its image. End aside.
However, this fact is less interesting than you might think. In fact, if $g$ is an arbitrary element of an arbitrary finite group $G$, and $r$ is the order of $g$, then the cycle structure of $g$'s translation action on $G$ is always $|G|/r$ cycles of length $r$, regardless of anything else about $G$ or $g$. In particular, you cannot use the fact that two elements of $G$ have the same cycle structure for the translation action to detect conjugacy, because all it means is that they have the same order. (Certainly conjugate elements have the same order, but not conversely.)
The reason why $g$'s (left) translation action on $G$ always looks like $|G|/r$ cycles of length $r$ is because these cycles are nothing but the (right) cosets of the subgroup $\langle g\rangle$ of order $r$ generated by $g$. Indeed, given $h\in G$, $g$'s left translation action sends $h\mapsto gh \mapsto g^2h \mapsto \dots\mapsto g^{r-1}h\mapsto h$.
Addendum: More generally, suppose you have identified $G$ with some subgroup of $S_n$ (whether via the left translation action used in the proof of Cayley's theorem, or some other way).
The essential truth you seem to be asking after is that elements conjugate in $G$ will have the same cycle structure as elements of $S_n$. This is true exactly by your reasoning. If $\varphi:G\rightarrow S_n$ is an isomorphism of $G$ into a subgroup of $S_n$, and $g,g'$ are conjugate i.e. there exists $h\in G$ with $hgh^{-1} = g'$, then $\varphi(h)\varphi(g)\varphi(h)^{-1} = \varphi(g')$ since $\varphi$ is a group homomorphism, so $\varphi(g),\varphi(g')\in S_n$ are conjugate, and this means they have the same cycle structure by your argument.
But it is not true that you can use this to detect conjugacy; i.e. elements not conjugate in $G$ may still have the same cycle structure in $S_n$.
Here is an illustration:
In $A_4$, the elements $(123)$ and $(132)$ are not conjugate, even though they have the same cycle structure. The problem is that, although there are permutations that carry the labels of one to the labels of the other (e.g. $(23)$), they do not lie in $A_4$. These elements become conjugate in $S_4$, but in the smaller group they are not conjugate.
Best Answer
Let $G= \mathbb{Z}_3 \times \mathbb{Z}_3 \times \mathbb{Z}_3$. Then for $a \in G$ we define $L_a: G \to G$ by $x \to ax$. It's obviously a permutation of $G$ (viewed as $27$-element set). Then we know that the map $\gamma: G \to S_{27}$ defined by $a \to L_a$ is a homomorphism. In fact this is what the Cayley's Theorem tells us.
Now we'll prove that all $L_a$ for $a\not = e \in G$ the permutation has the same cycle structure, which means that all permutations are in the same conjugacy class. In $G$ each such element $a$ has order $3$ and thus we have that $L_a \circ L_a \circ L_a(x) = x$ and thus it's not hard to conclude that $L_a$ consists of 9 3-cycles. Thus we have that all $L_a$ for $a\not = e \in G$ have the same cycle structres and therefore are in the same conjugacy class.
Finally note that $L_e$ is in a conjugacy class of it's own. Hence the proof.