Whatever spell or functions that you implement in TES you must keep in mind that you make this available for ALL characters, it's not like levitation, or open lock or any other spell is limited to mages alone. There is no categorization of mages, warriors or rogues, because I can easily build a character that is all three.
Levitation has obvious advantages both offensively and defensively for any style of character, so the only ones who wouldn't go for it are roleplayers who do the self-imposed limitation thing, and then we have yet another skill or feature that we need to avoid in order to keep the game fun. So next generation of super-characters will simply add alteration to the smithing/enchanting combo so now we have helicopter gunships...fun...
Yeah, they could add levitation as a master spell that you needed and a master level perk (branching from the expert perk) in Alteration to use. Maybe the spell would only give you slow fall without the perk and you need the perk to make it work for levitation. That would be available to all characters, but likely taken more by mages since it would require a substantial investment into Alteration perks to get there.
That would also solve the issues raised by earlier posters regarding the potential game breaking nature of the spell (sailing over drawbridges and up impassible cliffs), since by the time you get to Master level in just about any skill you are way overpowered in Skyrim, so being able to sail over drawbridges or hover over melee opponents and safely attack them with ranged weapons or spells would not be that much more OP than what you already have in the game with Shadow Warrior (with free sneak attack), high level Illusionists (muffle+invisibility) or plain old warriors with overpowered enchanted/smithed weapons.
As long as the spell was Master level and really hard to get (i.e., substantial perk investment required), those issues with it being overpowered are not really issues in a game like Skyrim where every high level character is overpowered in one way or another.
The issue about walled cities could be solved with an invisible loading zone that you pass through on your way into the city that loads the city.
Seems like it could work well enough without a major world redesign.