In reading this thread an idea has come to me. What if each of the travel powers had a 5th power (also available at 20th).
Flight - Supersonic Flight (A click power not a toggle with a Accolde like recharge.)
Teleport - A zone TP (ie from one zone to another, if a entrance is connected to present zone) or a Map click TP. Either could have the end cost and recharge time of a nova type power.
Super Jump - Another click power that works somewhat like flight for say 1 minute, again long recharge and high end use (although not nova like)
Super speed - No idea for this, but I'm sure someone can come up with something
I have no idea if any of these option are possible, but that is my 2 cents on this issue.