Go from Dash Boots to Ninja Tabi ASAP. Paladins have terrible movement for a melee class.

Soldier A-Abilities are really useful if the enemy is much higher level than you (and Mug is fun, even if you don't really need the money), since they work as equalizers, but otherwise they aren't worth the trouble.