(Written before clarification at end of question was added). Here is a result which seems to be of a somewhat negative nature in the context of your problem, and your suggested line of attack, I think. I will denote the number of conjugacy classes of $G$ by $k(G)$. The group $ G = {\rm SL}(2,2^{n})$ (n>1) is a triply transitive permutation group on $1+2^{n}$ points and has order $(2^{n}+1)2^{n}(2^{n}-1)$. It has $1+2^{n}$ conjugacy classes, so that $k(G) > |G|^{\frac{1}{3}}$. Furthermore, the only orders of centralizers of non-identity elements of $G$ are $2^n$,$2^{n}-1$ and $2^{n}+1$. Hence the minimum centralizer order for an element of $G$ is only marginally smaller than $|G|^{\frac{1}{3}}.$ Admittedly this is a rather special group and a rather rare situation, but it is an infinite family of "bad" examples.

Added later: come to think of it, there are even bad solvable examples. If we take any prime power
$p^{n}$ there is a doubly transitive solvable permutation group $G$ of order $p^{n}(p^{n}-1)$
and degree $p^{n}$(this is a Frobenius group which is the semidirect product of a vector
space of size $p^n$ acted on by a Singer cycle of order $p^{n}-1$. A point stablizer is
cyclic of order $p^n -1)$.` In this group, the only centralizer orders for non-identity
elements are $p^n$ and $p^{n}-1$. Hence the minimum centralizer order for $G$ is not
much less than $\sqrt{|G|}.$ So it seems that you can't expect to get much less than
$\sqrt{|G|}$ for the smallest centralizer order for $G$. I suspect that even this would
be very difficult to prove without the classification of finite simple groups.

Later remark: It is perhaps worth remarking explicitly here (though I am sure everybody knows it), that $S_n$ contains an element whose centralizer has order $n-1$ (and this is minimal),
and that for $n > 4$, $A_n$ contains an element whose centralizer has order $n-2$,
which is also minimal. Hence the "generic" highly transitive permutation group of degree $n$ behaves as hoped for large $n$ (and for sufficiently large $k$ there are no others, using the Schreir conjecture for $k >7$ or the disallowed Classification of finite simple groups for $k > 5$).