Normal subgroups in groups of odd order

Let $N$ be a cyclic group of prime order, and let $A$ be any group of automorphisms of $N$. Then the orbits of $N\setminus\{e\}$ under $A$ all have the same size. (The proof is easy, based on the fact that every element of $N\setminus\{e\}$ is a generator of $N$, and hence every element of $N\setminus\{e\}$ is a power of every other element.) Note that this holds for your counterexample: all the orbits have size $q$.

In particular, if $N$ is a normal subgroup of $G$, then taking $A$ to be $G$ acting by conjugation, we see that all conjugacy classes in $N\setminus\{e\}$ have the same size. Furthermore, if $N$ has odd order, then all these conjugacy classes have odd size. Finally, if the order of $N$ is a Fermat prime, then the only odd divisor of $\#N-1$ is 1. Therefore every element of $N$ is its own conjugacy class, hence is in the center.

(PS: No way I could have answered this question if you hadn't written it so well!)

Yes this holds for Fermat primes. You need the following observation. This is sometimes called the $N/C$ Theorem.

Lemma Let $G$ be a group with a subgroup $H$, then $N_G(H)/C_G(H)$ embeds homomorphically into Aut$(H)$.

Here $N_G(H)=\{g \in G : gH=Hg\}$, the normalizer of $H$ in $G$ and $C_G(H)=\{g \in G : gh=hg \text { for all } h\in H\}$, the centralizer of $H$ in $G$.

Now let us apply this to the situation where $N=H$ is normal, $|N|=$ Fermat-prime and $|G|$ is odd. Then $N_G(N)=G$ because of the normality of $N$. And since $N$ is cyclic, |Aut$(N)|$ is a power of $2$ (in fact $|N|-1$). It follows from the $N/C$ theorem that $|G/C_G(N)|$ is a power of $2$. But obviously it also divides $|G|$, which is odd. This can only be when $G=C_G(N)$, that is $N \subseteq Z(G)$.

So how do you prove the lemma? Let me give a sketch and leave the details with you: $N_G(H)$ acts as automorphisms on $H$ by conjugation. The kernel of the action is $C_G(H)$.

Generalizations:

Proposition 1 Let $G$ be a finite group, $N$ a normal subgroup of prime order $p$, with gcd$(|G|,p-1)=1$, then $N \subseteq Z(G)$.

Note that this holds for $p=2$: a normal subgroup of order $2$ must be central.

Proposition 2 Let $G$ be a finite group, $N$ a normal subgroup of prime order $p$, where $p$ is the smallest prime dividing $|G|$. Then $N \subseteq Z(G)$.