When is the conjugation character almost multiplicity free? Let me give some motivation, which also explains how I arrived at the question. We may let the finite group $G$ act on itself by conjugation, and this makes the group ring into a $\mathbb{Z}G$-module which affords character $ \theta = \sum_{\chi \in {\rm Irr}(G)}(\chi \overline{\chi}).$ It follows that for each irreducible character $\mu$ of $G,$ the Schur index $m_{\mathbb{Q}}(\chi)$ divides the multiplicity of $\mu$ in $\theta$, which is easily calculated to be $\sum_{i=1}^{k}
\mu(x_{i}),$ where $x_{1},x_{2},\ldots, x_{k}$ are representatives for all the distinct conjugacy classes of $G$ and $k = k(G)$ is the number of conjugacy classes of $G$. The multiplicity of the trivial character in $\theta$ is $k,$ and I'll say that $\theta$ is almost multiplicity free if only the trivial character occurs with multiplicity greater than one in $\theta.$
If we knew that $\theta$ was almost multiplicity free, then we could conclude that all its irreducible constituents would have Schur index one: so that leads to the question.
One easy observation is that if $G$ is a non-trivial $p$-group for some prime $p,$ then the conjugation character only has a chance to be almost multiplicity free if $G$ has nilpotence class at most $2.$ The character is clearly a multiple of the trivial character when $G$ is Abelian. Otherwise, any irreducible character of $G$ of degree divisible by $p$ is easily checked to occur with multiplicity divisible by $p$ in the conjugation character. On the other hand, if this multiplicity is zero for each non-linear irreducible character of $G,$ then the derived group $[G,G]$ is contained in the kernel of the conjugation  character, which is precisely $Z(G)$, so $G$ has class $2$. 
It seems to me that it is likely to be rare for the conjugation character to be almost multiplicity free. Apart from Abelian groups and the non-Abelian groups of order $8$ I am not aware of any other groups with this property, though I have not searched very hard. I am more interested in theoretical insights, but I am also interested in empirical evidence.
(Note added later: The answer of Mark Wildon leads to the fact that any extraspecial group of order $2^{2n+1}$ has an almost multiplicity free conjugation character. In fact, it implies that a $2$-group $G$ of class $2$ has an almost multiplicity free conjugation character if and only if $G$ is extra-special. I had better give my version of the argument in full, which benefits from insights provided by Mark's answer, since there has been some confusion in the earlier comments: note that $G$ has at most $[G:G^{\prime}] + \frac{(|G|-[G:G^{\prime}])}{4}$ irreducible characters. On the other hand, each non-linear irreducible character occurs with multiplicity zero in the conjugation character, as noted above, and each non-trivial linear character occurs with multiplicity at most $1$. Since the conjugation character has degree $|G|$ and the trivial character occurs with multiplicity $k,$ we have $|G| < k + [G:G^{\prime}].$ Hence $|G| < \frac{7[G:G^{\prime}] +|G|}{4}$, which gives $|G^{\prime}| <  \frac{7}{3}$, so $|G^{\prime}| = 2.$ Hence $|C_{G}(x)| \geq \frac{|G|}{2}$ for all $x \in G.$ It follows that $\theta = \frac{|G|}{2} 1_{G} + \frac{|Z(G)|}{2} \rho_{G/Z(G)},$ where $\rho$ denotes the regular character. This is almost multiplicity free if and only if $Z(G) = G^{\prime}$. Now the usual argument shows that squares are central in $G,$ so that $G/Z(G)$ is elementary Abelian, and $G$ is extra-special).
Later edit: By a result of Bob Guralnick and myself (which depends on the classification of finite simple groups), it follows that no non-Abelian finite simple group ( in fact no finite group with trivial Fitting subgroup) has almost multiplicity free conjugation character. For $\langle \theta,\theta \rangle = \sum_{i=1}^{k}|C_{G}(x_{i})| >  |G| + k$ for $|G| >2$ . On the other hand, if $\theta$ is almost multiplicity free, then we have $\langle \theta, \theta \rangle \leq k^{2} +k.$ Hence in that case we must have $k > |G|^{\frac{1}{2}}$, whereas Guralnick and I proved that $k(G) \leq |F(G)|^{\frac{1}{2}}|G|^{\frac{1}{2}}$ for any finite group $G,$ so $k(G) \leq |G|^{\frac{1}{2}}$ whenever $F(G) = 1.$ 
(Probably last edit): Peter Mueller pointed out that the symmetric group $S_{3}$ satisfies the condition. Let me flesh out the claim I made in comments that no other Frobenius group has an almost multiplicity free conjugation character, since F. Ladisch uses that in his definitive answer. Let $G = KH$ be a Frobenius group with kernel $K$ and complement $H.$
We recall thaat two elements of $H$ which are conjugate in $G$ are already conjugate inn $H,$ and tht every non-identity element of $G$ is conjugate either to an element of $H$ or an element of $K,$ but not both. 
Let $e = |H|.$ Then $G$ has $k(H) +\frac{|K|-1}{e}$ conjugacy classes. We note that if $\mu$ is an irreducible character of $G$ with $K$ in its kernel, then $\langle \theta, \mu \rangle$ is equal to $\mu(1)\frac{|K|-1}{e} +$ (the multiplicity of $\mu$ in the conjugation character of $H$). Since the last quantity is non-negative, we must have $|K| - 1 = e$ and $\mu(1) = 1$ (note that $\mu$ may be viewed as an irreducible character of $H).$
Thus $H$ is Abelian, and acts transitively on $K^{\#}$ by conjugation, which forces $K$ to be an elementary Abelian $p$-group for some prime $p.$ 
Now if $\chi$ is an irreducible character of $G$ which does not contain $K$ in its kernel, then $\chi$ vanishes identically outside $K$ and is induced from an irreducible character of $K,$ which we now know is linear. Thus $\chi(1) = e.$ Since $H$ acts transitively on $K^{\#},$ Clifford's Theorem tells us that $\chi(1) + e \chi(x) = 0$ for any $x \in K^{\#},$ so $\chi(x) = -1$ for each $x \in K^{\#}.$ Hence the multiplicity of $\chi$ in $\theta$ is just $e-1.$ Since $\theta$ is almost multiplicity free, we see that $e = 2$ and $|K| = 3$, as claimed.
 A: Extraspecial $2$-groups and $S_3$ are the only nonabelian examples.
We may write $\theta$ as a sum of the permutation characters on the orbits, which in our case are the conjugacy classes: In notation of the question,
$$ \theta = \sum_{i=1}^k (1_{C_G(x_i)})^G .$$
Suppose that $x$ and $y$ are not conjugate. If $\theta$ is almost multiplicity free, then the only common constituent of $(1_{C_G(x)})^G$ and $(1_{C_G(y)})^G$ must be $1_G$. Thus (by Frobenius reciprocity and Mackey)
$$ 1 = [(1_{C_G(x)})^G, (1_{C_G(y)})^G] 
     = \sum_t [ 1_{C_G(x)^t\cap C_G(y)}, 1_{C_G(x)^t\cap C_G(y)}], $$
the last sum running over double coset representatives with respect to $C_G(x)$ and $C_G(y)$. Thus $G$ has the following property: 

Property: If $x$ and $y\in G$ are not conjugate, then $G= C_G(x)C_G(y)$.    

The result follows from this apparently weaker property. (I didn't use that $(1_{C_G(x)})^G$ itself is multiplicity free.) Some first consequences: 


*

*If $g\not\in Z(G)$ and $k\in \mathbb{N}$, then either $g^k\in Z(G)$ or $g$ and $g^k$ are conjugate.  

*All elements outside the center have prime power order and prime order modulo the center. (Apply 1. to prime divisors of the order of $g$.)  

*Since elements in different cosets of $G'$ are not conjugate, it follows that $G/G'$ is elementary $2$-abelian.  

*If $g\not\in Z(G)$ and $z\in Z(G)$, then $g$ and $gz$ are conjugate. In particular, $Z(G)\leq G'$, if $G$ is not abelian.  


Thus if the prime $p$ divides $|Z(G)|$, then $G$ is a $p$-group (as $g$ and $gz$ have the same order by 4.), and thus by 3., $p=2$.  The exponent of $G/Z(G)$ is $2$ by no.2., so $G'=Z(G)$. It is easy now to see that $|Z(G)|=2$. (See Mark Wildon's answer or the proof in the question).  
It remains to do the case $Z(G)=1$. Let $g$ be an element of maximal order $p$ (a prime, by no.2.). Let $k\in \mathbb{N}$ have multipicative order $p-1$ mod $p$. Then $g$ and $g^k$ are conjugate (1.), via $x\in G$ (say). Then $g\in C_G(x^{p-1})$, but $g\not\in C_G(x^n)$ for any $n< p-1$. It follows that $x^{p-1}\in Z(G)=1$ and that $p-1$ is the order of $x$. But then $p-1$ is prime and thus $p=3$. Thus $G$ is a $2$-$3$-group.
Let $P$ be a Sylow $2$-subgroup and $Q$ a Sylow $3$-subgroup. Since all elements in $G$ have prime order, it follows that $C_G(x)\leq P$ for all $1\neq x\in P$. Therefore, by the above "Property", all elements of $P\setminus 1$ are conjugate in $G$. The same holds for $Q\setminus 1$, too. Since $G$ is solvable (Burnside), one of the Sylows is normal and $G$ is a Frobenius group. But then $G=S_3$ by Geoff Robinson's argument in the comments. (More directly, as $G/G'$ is a nontrivial $2$-group, we see that $Q$ is minimal normal. But then $|P|=2$ by a well-known property of Frobenius complements and since $P$ is elementary abelian, and $|Q|=3$ since $Q\setminus 1$ is a conjugacy class of $G$.)
A: Suppose that $G$ is a $p$-group such that the conjugation
character $\theta_G$ is almost multiplicity-free. This answer shows that $p=2$.
First of all I'll give my version of Geoff's proof that $G$ 
has nilpotency class at most $2$. By a comment in the question, 
$\langle \theta_G, \chi\rangle = \sum_{i=1}^k \chi(x_i) = 0$ 
whenever $\chi(1) > 1$.
Thus the sum of all entries in the character table of $G$
is equal to $\theta_G(1) = |G|$ and so, as in this paper by
Louis Solomon, if $g \in G'$ then
$$ \theta_G(g) = \sum_{\chi \in \mathrm{Irr}(G) \atop \chi(1) = 1} \Bigl( \sum_{i=1}^k \chi(x_i) 
\Bigr)
\chi(g) = \sum_{\chi \in \mathrm{Irr}(G) \atop \chi(1) = 1} \sum_{i=1}^k \chi(x_i) = |G|. $$
Hence $G' \le Z(G)$, as required.
Since $\theta$ is almost multiplicity-free, $\sum_{i=1}^k \chi(x_i) \le 1$
whenever $\chi$ is non-trivial. The sum of all the entries in
the character table is $|G|$, so $|G| \le k + (k-1) = 2k-1$. 
From $k \le |Z(G)| + (|G| - |Z(G)|)/p$ we get
$$ \frac{|G|}{2} + \frac{1}{2} \le k \le \frac{|G|}{p} 
+ \Bigl(1-\frac{1}{p}\Bigr) |Z(G)|. $$
Suppose that $G$ is non-abelian. Then the right-hand side is at most $2|G|/p$, and so $p \le 3$. If $p =3$ we have $|G|/6 + 1/2 \le 2|Z(G)|/3$ which implies $|G| + 3 \le 4|Z(G)|$. So $Z(G)$ has index at most $3$ in $G$. But then $G/Z(G)$ is cyclic, hence $G = Z(G)$.
Therefore, if $G$ is non-abelian then $p=2$. In my original answer I also claimed $|Z(G)| = 2$, but this now looks like a misreading of an inequality.
However, as Geoff points out in a comment, if $|Z(G)| = 2$ then
$G$ is an extra-special $2$-group, and in this case $\theta_G$ is
almost multiplicity-free.
