Your question can be rephrased as
For which $G$ is $|R_g(h)|=1$ for all $g,h\in G$?
or more generally
For which pairs $(H,G)$ with $H\trianglelefteq G$ is $|R_g(h)|=1$ for all $g\in G$, $h\in H$?
This can be answered completely as follows:
Lemma: If $h\notin Z(G)$ then $|R_g(h)|\ne 1$ for some $g\in G$.
Proof: We show this by contrapositive.
Suppose $|R_g(h)|= 1$ for all $g\in G$.
From this we show that $G=C_G(h)O_h$. Indeed for $x,y\in C_G(h)$ and $z\in O_h$ there is some $x'\in C_G(h)$ with $xy=x'z$ if and only if $x^{-1}x'y=z$ which holds if and only if $z\in O_h\cap C_G(h)y=R_y(h)$. But $y\in R_y(h)$ and $|R_y(h)|=1$ so this holds if and only if $z=y$. Hence $xy=x'z$ for some $x'\in C_G(h)$ if and only if $y=z$ and therefore $x=x'$. Hence $|C_G(h)O_h|=|C_G(h)||O_h|=|G|$ by orbit-stabiliser, so $G=C_G(h)O_h$.
Now consider the natural quotient map $\varphi:G\to G/C_G(h)$. We have $\varphi(O_h)=\varphi(G)=G/C_G(h)$. But $O_h=\{h^x|x\in G\}$ and for $x\in G$ we have $\varphi(h^x)=\varphi(h)^{\varphi(x)}=1$ so $\varphi(O_h)=1$. Hence $G/C_g(h)=1$ and $h\in Z(G)$.
Corollary: Let $H\trianglelefteq G$. Then $|R_g(h)|=1$ for all $g\in G$, $h\in H$ if and only if $H\le Z(G)$.
First, note that $\{e\}$ is always a conjugacy class in $H$. Since $H$ is normal, the requirement that $|O| = 2$ means that there is a conjugacy class $K$ such that $H = K\cup \{e\}$, and that $|H| = |K|+1$. Since we want $|K|^2 + 1$ to be prime, this means that $|K|$ is even and $|H|$ is odd.
Now, there are a number of statements that can be made about the restrictions on $(G,H)$:
- $G$ cannot be abelian, otherwise $|K| = 1$ and $2$ is not an odd prime.
- $G$ cannot be a finite $p$-group. If $p$ is odd, its normal subgroups intersect the center of $G$ nontrivially thus $H$ would contain at least $p$ conjugacy classes. Since $|H|$ is odd, $p$ cannot be even.
- $(G,G)$ cannot be a pair, as this would imply that $G$ is a $p$-group.
- $G$ cannot be simple and $H$ must be a proper normal subgroup since $(G,G)$ cannot be pair.
- $G$ cannot be quasisimple, as all proper normal subgroups must lie in the center of $G$ and thus have order two or have at least three conjugacy classes.
- $G$ cannot be a product $G_1\times G_2$ where $G_1$ and $G_2$ are $p_1$- and $p_2$-groups for distinct primes $p_1$ and $p_2$. Assume $(G_1\times G_2,H)$ is a pair, and let $\pi_i:G_1\times G_2\to G_i$ be the projection map for $i=1,2$. Since $|H|$ must have prime power, it must be a subgroup of $G_1\times\{e\}$ or $\{e\}\times G_2$. That means $(G_i, \pi_i(H))$ is a pair for some $i$. This is impossible since $G_i$ are $p$-groups.
Now, let's do some computations in common non-ableian groups and see what examples pop out.
Let's take $G = S_n$. Since $H$ is normal, we know that $H = A_n$. However, we know that $|H|$ is odd, which is only true for $A_n$ when $n\le 3$. Since $A_2$ is trivial, $A_3$ is the only possible candidate. It turns out that $(S_3, A_3)$ is a valid pair!
Now, let $G$ be the dihedral group
$$D_n = \langle a, x | a^n = x^2 = e, xax = a^{-1}\rangle.$$
Let's assume that $n$ is odd. The only normal subgroups of $D_n$ are then $\langle a^k\rangle$ when $k~|~n$, so $H = \langle a^k\rangle$. Moreover, there are two types of conjugacy classes: all elements not in $\langle a\rangle$, or pairs $\{a^k, a^{-k}\}$. Since the first type isn't a group when we add in $e$, it follows that we need $H = \{e, a^k, a^{-k}\}$. This implies that $a^k$ has order three, so $n = 3k$. Note that this pair $(D_{3k}, \langle a^k\rangle)$ for $n=3$ is exactly the $(S_3, A_3)$ example above.
If $n$ is even, there are two other types of normal subgroups possible: $\langle a^2, x\rangle$ and $\langle a^2, ax\rangle$. However, the conjugacy classes look like pairs $\{a^k, a^{-k}\}$ and the two sets $\{a^{2s}x|s\in\mathbb{Z}\}$, and $\{a^{2s+1}x | s\in\mathbb{Z}\}$. This means that neither $\langle a^2, x\rangle$ nor $\langle a^2, ax\rangle$ can be options for $H$ since they both contain more than two conjugacy classes. Thus, the only option is the same example as above, where $n = 3k$ and $H = \langle a^k\rangle$.
I haven't been able to find any examples where $|H|\ne 3$, and it seems like these pairs are going to be fairly rare. I'm curious if there are any nilpotent examples -- these groups are products of $p$-groups, and the last bullet point above makes it seem as though this is impossible.
Best Answer
Consider the application $$ f(a, g)=g^{-1}ag $$ then clearly $$ f(f(a, g), h)=f(a, gh) $$
If exists $g\in \mathcal F^{(a)}_b$ then $$\begin{align} h\in \mathcal F^{(a)}_b &\Leftrightarrow f(a, g)=f(a, h)\\ &\Leftrightarrow f(a, g)=f(f(a, hg^{-1}), g)\\ &\Leftrightarrow a=f(a, hg^{-1})\\ &\Leftrightarrow hg^{-1}\in C_G(a)\\ &\Leftrightarrow h\in C_G(a)g \end{align}$$ so if $F^{(a)}_b$ isn't empty there exists $g\in G$ such that $F^{(a)}_b=C_G(a)g$ then $$ \left\lvert F^{(a)}_b\right\rvert\, =\begin{cases} 0 & \text{if }\mathcal F^{(a)}_b\text{ is empty}\\ \lvert C_G(a)\rvert & \text{otherwise} \end{cases} $$
Observe that $b\neq b'$ implies that $\mathcal F^{(a)}_b\cap \mathcal F^{(a)}_{b'}=\emptyset$ so all non empty $\mathcal F^{(a)}_b$ determine a partition of $G$ so there're exactly $\lvert G : C_G(a)\rvert$ different $b\in G$ such that $\mathcal F^{(a)}_b$ is not empty.