Firstly, any finite non-Abelian $2$-group $G$ as in the last remark of the question has centre of index $4$. Suppose otherwise and set $Z= Z(G).$ Suppose that each element of $G \backslash Z$ has centralizer of index $2$. If $G$ has two different Abelian maximal subgroups $M$ and $N$ then $M \cap N = Z$ and has index $4$. If there is a unique
Abelian maximal subgroup $M$ of $G$, then for any $x$ outside $M$, we see that $<x> C_{M}(x)$ is Abelian, is different from $M$ and has index $2$ in $G$, a contradiction. Hence we may suppose that $G$ has no Abelian maximal subgroup.

By induction, we may suppose that $[M:Z(M)] = 4$ for each maximal subgroup $M$ of $G$, so every Maximal subgroup of any such $M$ is Abelian. But as above , we then see that for any $x$ outside $M$, the centralizer of $x$ in $G$ is an Abelian maximal subgroup of $G$, contrary to assumption.
Hence we do have $[G:Z] = 4, $ as claimed. Note thatvweay suppose that $Z \leq M, $ otherwise $G = ZM,$ and then
$ZX$ is a central subgroup of $G$ of index $4,$ where $X = Z(M).$

Here is a sketch proof that a group $G$ satisfying the first condition must be a $2$-group- well, strictly a direct product of a 2-group and an Abelian group of odd order. You want $G$ to have $|Z|+ 3|G|/8$ conjugacy classes, where $Z=Z(G)$. If we choose $G$ of minimal order subect to having this property, then $G$ can not be expressed in the form $A \times H$ for $A,H$ proper with $A$ Abelian, so suppose that this is the case.

Suppose now that $G$ is not a $2$-group. Then $G = SN$ where $S$ is a $2$-group and $N$ is a non-trivial normal $2$-complement. If $[S,N]= 1,$ then $G=S \times N,$ contrary to hypothesis. Hence $[S,N]$ has order $3$ or $5$, in which case $S$ is Abelian as $[G,G]$ has order at most $5$. It follows that $N$ is either a $3$-group or a $5$-group. Also $N$ must be Abelian, since we can't have $[S,N] \leq [N,N]$ by properties of coprime automorphisms.

Now $G = (S[N,S]) \times C_{N}(S)$ so $C_{N}(S) = 1$ and $Z = Z(G)$ is a $2$-group, and now $N = [N,S]$ has order $3$ or $5$.

Suppose that $|N| = 5.$ Now $G$ has $|S|$ linear characters and $\frac{15|S|}{8}+ |Z|- |S|$ non-linear irreducible characters, so that
$5|S| \geq |S| + d^{2}(\frac{7|S|}{8}+ |Z|)$, where $d$ is the smallest degree of a non-linear irreducible character of $G$, which is easily seen to force $d=2.$

This in turn forces $[S:Z]= 2$, which easily yields a contradiction.

Hence in the case under consideration, we must have $|N| = 3,$ and then again $[S:Z]=2.$ But now, each non-linear irreducible character of $G$ has degree $2$ by a Theorem of Ito, and we
have $3|S| = |S| + 4(\frac{9|S|}{8} -\frac{|S|}{2}),$ which is a contradiction.