We call a finite group $G$ normal if for all $s,r\in G$, if $\langle gsg^{-1}:g\in G\rangle =\langle grg^{-1}:g\in G\rangle $ then there exists $x\in G$ such that $\langle r\rangle =\langle xsx^{-1}\rangle $.
Abelian groups are normal groups and symmetric groups $S_n (n\geq 5)$ are not.
Is a $p$-group necessarily normal?
What is the largest family of normal groups?
Normal groups are necessarily solvable. Indeed, by Jordan-Holder decomposition an unsolvable finite group $G$ necessarily contains a normal subgroup $H$ that maps surjectively to a nonabelian finite simple group $S$. Take $H$ minimal with this property.
$S$ is not a $p$-group for any $p$, hence its order has two distinct prime factors $p_1$ and $p_2$. By Cauchy's theorem, it contains elements $g_1$ and $g_2$ of orders $p_1$ and $p_2$. Let $r_1$ be an inverse image of $g_1$ in $H$, chosen to have $p_1$-power order (possible by taking an arbitrary lift and taking a suitable prime-to-$p_1$ power of it). Let $r_2$ be the same for $g_2$.
Then the normal subgroup generated by all the conjugates of $r_1$ is $H$. Indeed, it is manifestly contained in $H$, as $H$ is normal and contains $r_1$. Its image under the projection to $S$ is some normal subgroup of $S$ containing $g_1$, hence all of $S$. By minimality of $H$, it is $H$. Then the same is true for $r_2$.
But $r_1$ and $r_2$ have distinct orders, hence the cyclic subgroups they generate cannot be conjugate.
However, normal groups need not be nilpotent. Consider the group of all affine transformations of $\mathbb F_q$, aka $\mathbb F_q \rtimes \mathbb F_q^{\times}$. All elements of order $p$ are conjugate and generate the subgroup $\mathbb F_q$, and all nontrivial elements of prime-to-$p$ order $n$ are conjugate and generate the inverse image of the subgroup of $n$th roots of unity in $\mathbb F_q^{\times}$.
Here's a counterexample. Let $p$ be any prime; let $G$ be the upper unipotent group in dimension 4 over the field $F_p$ ($G$ has order $p^6$). Then $G$ does not satisfy the property you call "normal", i.e. $G$ has two non-conjugate cyclic subgroups with the same normal closure.
For $i<j$, let $e_{ij}=1+E_{ij}\in G$ be the elementary matrix (1 on the diagonal and at the entry $ij$, 0 elsewhere). The center of $G$ has order $p$ with generator $e_{14}$. Let $U$ and $V$ be the cyclic subgroups generated by $e_{23}$ and $e_{23}e_{14}$ respectively (both have order $p$). Since $U$ and $V$ coincide modulo the center and since, in every nilpotent group, every nontrivial normal subgroup of $G$ has nontrivial intersection with the center, $U$ and $V$ have the same normal closure.
We claim that $U$ and $V$ are not conjugate. Indeed, otherwise, $e_{23}$ is conjugate to some power $(e_{23}e_{14})^k$ ($1\le k\le p-1$), and projecting on the abelianization shows that $k=1$. So, for some $g$, we have $ge_{23}g^{-1}=e_{23}e_{14}$. But a direct computation shows that if $g=\begin{pmatrix}1 & a & * & *\\ 0 & 1 & b & *\\ 0 & 0 & 1 & c\\ 0 & 0 & 0 & 1\end{pmatrix}$, then $e_{23}^{-1}ge_{23}g^{-1}=\begin{pmatrix}1 & 0 & a & -ac\\ 0 & 1 & 0 & c\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\end{pmatrix}$. The latter matrix cannot be equal to $e_{14}$ and we have a contradiction; thus $U$ and $V$ are not conjugate.
The smallest counterexample to the question about whether all $p$ groups are normal.is SmallGroup(32,11). It has two non-conjugate cyclic subgroups of order $4$ with the same normal closure of order $16$.
I think that it is always a good idea to do a quick computer check for small counterexamples before making conjectures about finite groups.
Since Will Sawin suggested I expand my comment, here goes (my starting point is that Will has already proved that a "normal" finite group $G$ is solvable).
Let $M$ be a minimal normal subgroup of a "normal" group $G$. Then $M$ is an elementary Abelian $q$-group for some prime $q$, as $G$ is solvable. Let $r,s$ be any two non-identity elements of $M$. Then $M = \langle grg^{-1} : g \in G \rangle$ and $M = \langle gsg^{-1} : g \in G \rangle$ (both subgroups are contained in $M$, neither is the identity, and $M$ is minimal normal). By the definition of a "normal" group $G$, we have $\langle r \rangle = \langle xsx^{-1} \rangle$ for some $x \in G$. Hence the subgroups $\langle r \rangle$ and $\langle s \rangle$ are $G$- conjugate. Thinking of $M$ as a vector space over $\mathbb{F}_{q}$, we see that $G/M$ acts (via conjugation action) as a group of linear transformations of $M$ which is transitive on $1$-dimensional subspaces. This puts quite strong restrictions on $G/C_{G}(M)$
Now suppose that $X$ is a solvable doubly transitive permutation group, and let $V$ be a minimal normal subgroup of $X$. Then $G = VH$ where $H$ is a point-stabilizer in the permutation action, and $V \cap H = 1$. B. Huppert classified such $X$: note that $V$ may be identified with the set on which $X$ acts doubly transitively, and this extends the regular action of $V$ on itself. Hence $H$ must act transitively on $V^{\#}$, the set of non-identity elements of $V$.
It may be worth remarking that in general, if $Y$ is a finite solvable group with a unique minimal normal subgroup $U$ such that $Y$ acts transitively on non-identity cyclic subgroups of $U$, and semi-regularly on non-identity elements of $U$ and $Y/U$ is a "normal" solvable group, then $Y$ is "normal". To see this, let $T$ be a complement to $U$ in $Y$ (all of these are conjugate under the hypotheses, as $[Y:U]$ and $|U$ must be coprime). Then $T$ is a "normal" group in its own right by isomorphism theorems. The hypotheses also imply that every element of $Y \backslash U$ has order prime to $p$, where $U$ is a $p$-group.
Hall's theorems then imply that every element of $Y \backslash U$ is conjugate to an element of $T$. Furthermore, two subgroups of $T$ are $Y$-conjugate if and only if they are already $T$-conjugate.
Let $N$ be a proper non-identity normal subgroup of $Y$. Then $N$ must contain $U$ by the uniqueness of $U$. Then $N = UM$ where $M$ is a uniquely normal subgroup of $T$.
Now let $r$ and $s$ be non-identity elements of $Y$ with the same normal closure. If $r,s \in U$, then we know that $\langle r \rangle$ and $\langle s \rangle$ are $Y$-conjugate. Hence we may suppose that $r$ and $s$ both lie outside $U$.
Otherwise $\langle rU \rangle $ and $\langle sU \rangle$ are conjugate by "normality" of $Y/U$. The hypotheses also imply that all elements of $rU$ have order prime to $p$, and are conjugate via an element of $U$. Hence we may suppose that $r,s \in T$, and are $T$-conjugate. Thus $Y$ is "normal".
