the only good way to play a paladin is mounted combat. it literally is the only reason to take paladin past level 2 or 3 tops. so go paladin 5/cavalier10 then whatever else.

wanna be a pirate? have an aquatic mount. on a boat? flying mount works too