Existence of a subgroup $H$ of a finite group $G$ with $|H|>\sqrt{|G|}$

Let $k \in N \setminus Z(G)$ and let $K$ be the conjugacy class of $k$ in $G$.

Then $|G|/|C(k)|=|K|<|N|$. Therefore $|G|<|N||C(k)|$ and at least one of $N$ and $C(k)$ has order greater than $\sqrt{|G|}$.

The conjugation action of $G$ permutes the conjugacy classes of $N$ and since the classes are all fixed by $N$, we get an induced action of $G/N$ on these classes. Furthermore, for $g \in N$, the index $|C_G(g):C_N(g)|$ is equal to the stabilizer of the conjugacy class ${\rm Cl}_N(g)$ of $g$ in $N$ under this action of $G/N$.

Let $g \in N \setminus Z(G)$. Then there are at most $|N|/|{\rm Cl}_N(g)| = |C_N(g)|$ conjugacy classes in $N$ having the same size $|{\rm Cl}_N(g)|$ as the class of $N$, and so (using the fact that $g$ is not conjugate to $1$) the number of such classes in the orbit of the conjugation action of $G/N$ is strictly less than $|C_N(g)|$.

So the stabilizer of the class of $g$ under this action of $G/N$ is greater than $|G||/(|N||C_N(g)|)$.

So $|C_G(g)|/|C_N(g)| > |G||/(|N||C_N(g)|)$ and hence $|N||C_G(n)| > |G|$. So at least one of $N$ and $C_N(g)$ must have order greater than $\sqrt{|G|}$.