You are correct: the units must indeed match. If we take a standard evolution with unitary $U=\exp(-i H \theta)$, then the units of $H$ and $\theta$ must match such that $H\theta$ is unitless. For a pure state $\rho_\theta=U|\psi\rangle\langle\psi|U^{\dagger}$ with unitary evolution, the quantum Fisher information takes the form $$F_Q[\psi,H]=\langle\psi|H^2|\psi\rangle-\langle\psi|H|\psi\rangle^2.$$ The quantum Fisher information has the same units as $H^2$. We already know that $H\theta$ is unitless: this implies that $H^2\theta^2$ is also unitless, so the units in the quantum Cram'er-Rao bound work out just fine.
This can all be extended to mixed states and arbitrary generators without any problem.
The crucial point is realizing the conventions for the units when we write things like $\exp(-i H\theta)$. Does $\theta$ have dimensions of time? Have we set $\hbar$ to unity? Are we measuring energy in terms $\hbar\omega$ for some energy level? These are all crucial considerations. For example, the $N^2$ in the Heisenberg limit is really saying something about energy squared, and that is related with $\hbar$ to time squared, so things will work out, but one must be careful about all of these details.