The thing about the Coulomb gauge is that, in vacuum, you get both $A_0 = 0$ and $\nabla \cdot \vec A = 0$, so it eliminates the $(A_0,\pi^0)$ d.o.f. right out of the gate - we just have $A_0 = 0,\pi^0 = 0$ consistently and only need to care about the spatial parts, and due to $\nabla\cdot \vec A= 0$, the whole thing is just a bunch of oscillators in Fourier space, where the condition $\vec p \cdot \vec A(\vec p) = 0$ then eliminates one of the three remaining degrees of freedom. Note that because the Coulomb gauge has broken Lorentz covariance anyway, we don't care that this elimination of d.o.f. is not stable under Lorentz transformations.
The Lorenz gauge, in contrast, is a Lorentz invariant gauge condition and hence we're not allowed to just "eliminate $A_0$" or something because what's $A_0$ in one frame is a linear combination of all the $A_\mu$ in another - the point of picking the Lorenz gauge is precisely to preserve Lorentz covariance. So in a way the "difficulty" isn't as much down to specifics of the gauge condition as it is to us trying to do things covariantly vs. non-covariantly, but either way the core difference is that we're not allowed to drop the 0-th d.o.f., which really make the whole thing much simpler in the Coulomb gauge.
Additionally, the Lorenz gauge indeed does not completely remove gauge freedom since it remains invariant under harmonic gauge functions, see this question and its answers.