I like all the visual ideas people are suggesting. There were four basic movement types in CoX (run fast on the ground, fly in any direction in the air, jump really high with some direction change mid-jump possible, zap from place to place). I liked the hybrid movements (ninja run, for example) and the macros for teleporting through the air.
The wall-crawling and web/vineslinging ideas introduce a different mechanic, requiring you to be near a vertical surface. I'm not sure how easy that would be to implement, but it would be really cool. Or, you could just animate the vines going up and have them go nowhere, and have it be sort of a sine-wave flight path.
Another completely different mechanic I thought of would be to base some travel powers on an alternate "ground" (or two or three, different layers in each zone for each different travel power), an invisible layer (with hills and valleys) above the ground. Maybe a hoverboard can only go so far from the ground, sort of like a landspeeder, or higher, like an ultralight (don't want to fly too high in one of those things). Disengaging the power would glide you down to the ground on a path from wherever you were. So, kind of a superjump that gets you to a certain height and then moves you along at the top of your curve, following the contours of an invisible second ground, until you disengage the power. Maybe one power wouldn't go up buildings but would give you more speed and would use a low "invisible ground" as its guide. Maybe another would allow you to change direction with the contour of buildings and zoom up them and down them at a higher "invisible ground". Maybe another could be like grabbing a cosmic zipline that would take you way up near the roof of the world and move you quite quickly but when you descend you land somewhat randomly and can't avoid mobs as easily. Some ideas.