How about if I make Wings of the Eagle level 2, and add a spell like this to level 1?

Unfettered Stride

School Transmutation
Level Paladin 1

Casting Time 1 standard action
Components V, DF

Range Self
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).