So the client wants a multi-colored background (think 4 colors of paint splats randomly all over the page. Because of this the headers are a bit hard to read. I've currently got them set up as black text with some white drop shadow, but it's still pretty hard to read in IE. How can I make the headers legible regardless of what is behind them (it's a CMS so position on the page is liable to change regularly)?
Hmm... readability is essential, and part of design. I think better change background to a more readable format.
There are no magical rules for making fonts readable. Good contrast with background, nice size and leading, nice fonts... Good choices makes the readability. If background is your problem, try changing other text aspects, or try to change the background, at least on headers.