How about if I make Wings of the Eagle level 2, and add a spell like this to level 1?
Level Paladin 1
Casting Time 1 standard action
Components V, DF
Duration 1 minute/level
Your movement is not affected by difficult terrain. In addition, you gain a +1 Sacred Bonus to saving throws against effects that would impede your movement (such as entanglement). This bonus increases for every three caster levels you have (at least +1, maximum +3).