why exactly does Cadmium have a large natural linewidth?
I don't known exactly, but natural linewidths are caused by how many decay channels a state has. That is, how many transitions exist that can make you change state. Probably the energy level structure of Cadmium is complex enough that it allows a myriad transitions, which is likely since Cadium is not an alkali and hence not "trivial" with one electron in the outer shell.
The uncertainty principle thing is just another way of stating the frequency spread. If there are many decay channels, then it is more likely the state will decay, hence a short lifetime. With a short lifetime, there is not enough time to develop a clean and clear frequency signal, hence the spread spectrum.
why does a large linewidth mean that it's harder (need a higher field
gradient) to get the same amount of Zeeman shift?
Because you want to make sure that the energy level separation due to Zeeman is larger that the natural linewidth. The natural linewidth is basically blurring your energy level - so even if Zeeman is lowering/raising it up say 10 MHz, if the state is still "spread out" by 90 MHz then it's not seeing the Zeeman shift as a dominant effect. You want a high enough field so that the separation between states is $>>$ than 90 MHz, so as there to be a clean and net separation between states.