I mentioned fighter but fighter also lacks hide so it isn't much better. I went with cleric because it can fill that role: evil, deals with undead, divine casting. I know fighter can hit the feats easier, but fighter doesn't have the feel. I went through 6+ splats before I gave up on a better fit. I considered hexblade, but it seemed worse than fighter.
I did mention those levels, but they are buried in the middle somewhere. I think those levels make for the best reason to enter as paladin. However, I think you are better off with paladin levels.