I have to second Bone Knight. The steed advances as a special mount, and stacks with any paladin levels you have. I play a Fallen Paladin 10/Bone Knight 8 in one campaign. Not the most optimal build, but it's fun.

The Bone Knight gets some unique undead-based abilities as well that helps fit with the whole undead shtick, as well as having most of the Paladin class skills without being bound to a code if you have fallen paladin levels.