HINT: Try to prove that for $n \ge 5$, $A_n$, the alternating group of $n$ elements is the only proper and nontrivial normal subgroup of $S_n$.
UPDATE: This has to do something with the fact that $A_n$ is simple for $n \ge 5$. After proving this and checking the cases $n \le 4$ we can conclude that a normal subgroup of symmetric group has order $1, 4, \frac{n!}{2}$ or $n!$. Hence...
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
The following question from MathOverflow should answer your questions and more: Smallest permutation representation of a finite group?
The answer to 3) is yes, and more generally if $G$ is a finite abelian group such that
$$G \cong \mathbb{Z}_{p_1^{a_1}} \times \cdots \times \mathbb{Z}_{p_t^{a_t}}$$
where $p_i$ are prime and $a_i \geq 1$, then the minimal $n$ is $p_1^{a_1} + \cdots + p_t^{a_t}$. A proof can be found in the following paper that Jack Schmidt mentions in his MO answer.