Nice question! The $n = 3$ case is fun and I think small values of $n$ are going to make very good exercises so I encourage you to work on them yourself, but if you really want to know a solution....
If $H_1, H_2$ denote the stabilizers of the non-identity conjugacy classes with $|H_1| \le |H_2|$, then the class equation reads $|G| = 1 + \frac{|G|}{|H_1|} + \frac{|G|}{|H_2|}$, or
$$1 = \frac{1}{|G|} + \frac{1}{|H_1|} + \frac{1}{|H_2|}.$$
The reason this is useful is that if either $|G|$ or $|H_1|$ gets too big, then the terms on the RHS become too small to sum to $1$. Since we know that $|G| \ge 3$, it follows that we must have $|H_1| \le 3$; otherwise, $\frac{1}{|H_1|} + \frac{1}{|H_2|} \le \frac{1}{2}$ and the terms can't sum to $1$.
Now, if $|H_1| = 2$ then $|H_2| \ge 3$, hence $|G| \le 6$. Since every group of order $4$ is abelian we can only have $|G| = 6, |H_2| = 3$. The unique nonabelian group of order $6$ is $S_3$, which indeed has $3$ conjugacy classes as desired.
If $|H_1| = 3$, then $|G| \ge 3$ implies $|H_2| \le 3$, hence $|H_2| = |G| = 3$ and $G = C_3$.
There are at least two possible proofs, one of them by enumeration and
another one using the exponential formula.
By enumeration, first choose the elements to go on each cycle
(multinomial coefficient):
$$\frac{N!}{\prod_j (j!)^{P_j}}$$
Each of these elements generates $j!/j$ cycles (in placing labels on a
directed cycle all orbits under the action of the cyclic group have
the same size which is $j$):
$$\prod_j \frac{(j!)^{P_j}}{j^{P_j}}$$
Permutations of the size $j$ cycles are not distinguished:
$$\prod_j \frac{1}{P_j!}.$$
This yields the answer
$$\frac{N!}{\prod_j (j!)^{P_j}}
\prod_j \frac{(j!)^{P_j}}{j^{P_j}}
\prod_j \frac{1}{P_j!}
= \frac{N!}{\prod_j j^{P_j} P_j!}.$$
The second proof uses the exponential formula (OGF of the cycle index
of the symmetric group)
$$Z(S_N) = [z^N]
\exp\left(a_1 z + a_2 \frac{z^2}{2} + a_3 \frac{z^3}{3} + \cdots\right).$$
Extracting the coefficient of $[z^N a_1^{P_1} a_2^{P_2} \times\cdots]$
in $N! Z(S_N)$ we get
$$N! [z^N] [\prod_j a_j^{P_j}] \prod_j \exp\left(a_j\frac{z^j}{j}\right)
= N! [z^N] \prod_j \frac{z^{j P_j}}{j^{P_j} P_j!}
\\ = N! [z^N] z^{\sum_j jP_j} \prod_j \frac{1}{j^{P_j} P_j!}
= N! \prod_{j} \frac{1}{j^{P_j} P_j!},$$
the same as in the first version. (Here we take $P_j = 0$ for a cycle
size that is absent.)
Remark. The reason for treating the OGF like an EGF is that we
have the labeled species
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{SET}(
\mathcal{A_1}\textsc{CYC}_{=1}(\mathcal{Z})
+ \mathcal{A_2}\textsc{CYC}_{=2}(\mathcal{Z})
+ \mathcal{A_3}\textsc{CYC}_{=3}(\mathcal{Z})
+ \cdots)$$
and hence we are extracting from an EGF.
Best Answer
A property of subgroups is that for $H,K \leq G$ and $H\subseteq K$, then: $$ |G|=[G:K]\cdot[K:H]\cdot|H| $$
Since $Z(G)\subsetneq C_G(x)$ in general, then: $$ |G|=[G:C_G(x)]\cdot[C_G(x):Z(G)]\cdot|Z(G)| $$ So $n=[G:C_G(x)]\cdot[C_G(x):Z(G)]$ and therefore $[G:C_G(x)]$ divides $n$.