Allowing Fly to work in more quests doesn't mean that you need to use fly in all those quests. It just means they're built in a way that makes them non-exploitable via the Fly spell.
D&D levitate doesn't work that way. It allows you to move directly up and down and that's all.
And I disagree with your assessment. There are, in fact, entire sections of D&D books on how to create adventures that take into account the PC's access to "travel" magic and still be challenging. One of the things they (obviously) suggest is setting up certain kinds of hazards that prevent the spells (or whatever) from working. It shouldn't be the only thing you do, but why shouldn't use do it sometimes?
For instance, if I were an Evil Genius, I might put a permanent Anti-Magic field over the lava pit in my lair. I mean... why wouldn't I?![]()