Centralisers in the symmetric group Let $G$ be a $k$-transitive subgroup of the symmetric group $Sym(n)$, $k\geq 2$, $n$ large. (Make $k$ larger if you think it necessary to make the question below non-trivial/interesting.)
Write $C(g)$ for the centraliser of an element and $|C(g)|$ for its number of elements.
What can you say about $\min_{g\in G} |C(g)|$, relative to the size of $G$? Must it be small?
(Note that $k\geq 2$, $n\geq 3$ immediately imply that $G$ is non-abelian (thus making the question possibly non-stupid).)
(I should clarify that I expect (hope?) the answer to be quite a bit smaller than $\ll_{\epsilon} |G|^{\epsilon}$. (Assume $k\geq 3$ or $k\geq 4$ if needed.) In this, a $k$-transitive permutation group feels like a different sort of animal from a linear algebraic group $G$, where $|C(g)|$ is most often no smaller than $|G|^{\dim(T)/\dim(G)}$ ($T$ = a maximal torus of $G$).)
 A: (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$).
A: One possible approach - which would probably give non-optimal but non-trivial bounds - is to look at the number of conjugacy classes $Cl(G)$ in $G$.
Say the number of conjugacy classes $|Cl(G)|$ is $\leq K$. Then, by pigeonhole, there is a conjugacy class $Cl(g)$ with $\geq |G|/K$ elements. By the orbit-stabiliser theorem, we must then have $|C(g)|\leq K$ for some element $g$ of $G$.
Question: what upper bounds can one prove on $|Cl(G)|$ (relative to the size of $G$) without using the classification theorem? 
