IMC, instead of the immunity to disease and Remove Disease abilities, Paladins choose one Domain of their patron deity, getting the usual granted power and domain spells. It's an overall increase in power, so to compensate we switched Smite Evil to Smite Chaos. It's a bit less consistently useful.
The result has been a big improvement, IMO, since it means you can see Paladins with some Fire abilities, or Plant, or whatever. Some domains improve their class skill list, which frankly needed a boost. But anyway, if you want to have your elemental Paladins, you just need to pick the right domains.
We also totally reworked the Mount rules, but that's another topic entirely, one which I've already posted on this board a few months ago.