Fly is decently usable in battle, but it has its own issue in that it basically forces you to have a Flying-type (or the occasional non-Flying-type that does learn it) on your team in order to make use of fast-travel… either that, or you have to pull something that can learn it out of your PC every time you want to fly somewhere, which isn’t very, well… fast.
There's more to HMs than just the basic mechanical elements. For all their faults, it is nice to feel like you're actually working with your Pokemon to overcome obstacles in the overworld, particularly when you're in some super remote dungeon.
People say this a lot, and fair enough to those who feel that way, but it’s never really resonated with me. I like puzzle-solving, but being obligated to teach a certain move that my Pokémon is going to be stuck with for the duration of the dungeon in order to solve the puzzle doesn’t give me a satisfying feeling of cooperation; it just feels inconvenient.
I would say I get a perfectly sufficient sense of bonding with my own Pokémon by using them in battle as I go through the dungeon. They’re still essential to the player’s progress in that regard; it’s not as if they’re just languishing away in your pocket while you’re carried through the cave or across the ocean by a rental.
On top of that, part of the reason why I don’t feel that sense of connection is also because the presentation with HMs has always been pretty lacking — ironically, it wasn’t until the Ride Pager that you actually
saw the specific Pokémon performing the task. Like, when you use Strength, you get a quick glance at your Pokémon’s sprite, but then it’s
you who’s kicking the boulder around. With Machamp Shove, you see the Machamp helping you and putting in the work. With Surf and Fly, it’s just a generic sprite. Nothing to differentiate from a random Lapras or bird Pokémon that could have just been sent to you via something like the Pager. Cut, Rock Smash, Defog, etc.? Just that quick glance at the sprite, then the HM action is applied. No real action on the part of your Pokémon.
Plus… I think the existence and commonality of HM slaves says something about how strong of a bond players typically build with their Pokémon on the basis of HMs. Are they really feeling closer to that random Lv5 Zigzagoon that they’re just dragging around in order to get through a cave and putting no other investment into? Do they feel like that’s a satisfying way to solve puzzles in coordination with their Pokémon?
The fact that HMs are actual moves is what makes them so much more interesting imo. They aren't just "the thing you use to bypass an obstacle", they're "a move which you can actually use in battle that also serves the purpose of overworld exploration". It gives them a much more multipurpose feel
I think Hugin covered my thoughts on this fairly comprehensively. I think moves having field effects is cool and a nice way to add dimension to certain moves, but when those kinds of moves are
required for progression, it turns into a headache.