Here is a construction. We begin with a lemma:
Lemma. Let $N\triangleleft G$ be finite groups with $p:=[G:N]$ a prime number. Conjugacy classes of elements of $G-N$ have the same cardinality iff $|N\cap C_G(g)|$ does not change as $g$ varies in $G-N$.
Proof) For any $g\in G-N$, $NC_G(g)$ is a subgroup strictly containing $N$, hence $NC_G(g)=G$. Thus
$$
C_p\cong\frac{G}{N}=\frac{NC_G(g)}{N}\cong \frac{C_G(g)}{N\cap C_G(g)}\Rightarrow
|N\cap C_G(g)|=\frac{|C_G(g)|}{p}.
$$
Next, let $N$ be a finite group and $\phi:N\rightarrow N$ an automorphism satisfying the following:
- $\phi$ is of order $p$, and for any $n'\in N$ and $i\in\{1,\dots,p-1\}$ one has $|{\rm{Fix}}(u_{n'}\circ\phi^{\circ i})|=|{\rm{Fix}}(\phi)|$ where $u_{n'}$ is the inner automorphism $n\mapsto n'nn'^{-1}$ of $N$ and ${\rm{Fix}}$ denotes the set of fixed points. $(\star)$
(Notice that $\phi$ must be outer.)
Claim. When $N$ satisfies $(\star)$, the semidirect product $G:=N\rtimes_\phi C_p$ has the desired property.
Proof) Identify $N$ with an index $p$ subgroup of $G$, and let $g_0\in G-N$ be an element for which the induced automorphism $n\mapsto g_0ng_0^{-1}$ of $N$ coincides with $\phi$. Elements of $G-N$ may be uniquely written as $n'g_0^i$ where $i\in\{1,\dots,p-1\}$ and $n'\in N$. By the lemma, it suffices to show that the size of $\{n\in N\mid n(n'g_0^i)=(n'g_0^i)n\}$ is independent of the element chosen from $G-N$. Notice that $n(n'g_0^i)=(n'g_0^i)n$ may be written as $n'(g_0^ing_0^{-i})n'^{-1}=n$, or $u_{n'}\circ\phi^{\circ i}(n)=n$. Therefore, the preceding set is always of size $|{\rm{Fix}}(u_{n'}\circ\phi^{\circ i})|=|{\rm{Fix}}(\phi)|$.
We now discuss examples of $(N,\phi)$ which satisfy $(\star)$. A simple case, mentioned in the comments, is when $N$ is abelian. In that case, inner automorphisms are trivial and one needs to have $|{\rm{Fix}}(\phi^{\circ i})|=|{\rm{Fix}}(\phi)| \,\forall i\in\{1,\dots,p-1\}$ which clearly holds for any automorphism $\phi:N\rightarrow N$ whose order is a prime number $p$.
Here is a more complicated example with $N$ non-abelian: Suppose $p$ is odd, and take $N$ to be the group $\Bbb{Z}/p^2\Bbb{Z}\rtimes\Bbb{Z}/p\Bbb{Z}$ of order $p^3$ whose product rule is given by
$$
(u,v)*(s,t)=(u+(pv+1)s,v+t).
$$
We claim that the automorphism $\phi$ defined by $(1,0)\mapsto (1,1)$ and $(0,1)\mapsto (0,1)$ satisfies $(\star)$. First, notice that $\phi$ is of order $p$: A straightforward induction shows that
$$
\phi^{\circ k}(1,0)=(1,k),\quad \phi^{\circ k}(0,1)=(0,1).
$$
In particular, $\phi^{\circ p}$ is identity since it fixes both $(1,0)$ and $(0,1)$. Finally, we verify $|{\rm{Fix}}(u_{n'}\circ\phi^{\circ i})|=|{\rm{Fix}}(\phi)|$ for $i\in\{1,\dots,p-1\}$. Inner automorphisms of $\Bbb{Z}/p^2\Bbb{Z}\rtimes\Bbb{Z}/p\Bbb{Z}$ do not change the second component while the second component of $\phi(u,v)$ is $u+v$. Comparing second components, $u_{n'}\circ\phi^{\circ i}(u,v)=(u,v)$ requires $iu+v=v$, or $u=0$. Conversely, any element of $\Bbb{Z}/p\Bbb{Z}$ is fixed by $\phi$ and inner automorphisms. We conclude that ${\rm{Fix}}(u_{n'}\circ\phi^{\circ i})$ always coincide with the subgroup $\Bbb{Z}/p\Bbb{Z}$ of $N=\Bbb{Z}/p^2\Bbb{Z}\rtimes\Bbb{Z}/p\Bbb{Z}$.
