I always felt like the game would be better if they kept the HM obstacles but let you teach HMs into a separate move pool. Like, each of your Pokemon would have a second move set of just "exploration moves," which would ONLY be useable in the field. where you could put HM moves so they don't waste space in battle but could still be used.
Alternately, even, just have each Pokemon learn them naturally as non-move abilities. Like it seems kind of silly that not ALL Aerodactyls can Fly without being taught, after all.
In either case, it would be disappointing to see moves like Surf and Waterfall taken out, but then again it could also add some variety to the game. Maybe Surf is too reliable. And besides, we have Scald now. Maybe they'd even be replaced by other moves.
I agree that exploration feels a bit too easy without this stuff, but I also would HATE to go back to NEEDING to waste moveslots on HMs. Four moves is barely enough as it is.
The alternative of 'here we are dancing around for no reason, soon we will leave for no reason' NPC roadblocks is just terrible and lazy. Its honestly the most obnoxious part of the story in 5th gen. Seeing a tree you can't cut down or a rock you can't push out of the way doesn't give you the impression that the only reason you're unable to advance is because the game is forcing you along a specific path because they can't possibly trust you to forge your own way through the game and potentially get beaten down by higher-level trainers.
HMs add exploration and turn the overworld into something other than a 'walk, battle, talk, repeat' snorefest by including puzzles. The only real reason to hate them is the fact that they are underpowered in battle. They could easily fix that by raising their power (but not so much so that you'll be doing nothing but using HM moves in battle) so they aren't a waste of a moveslot in battle like all the not-waterfall/surf HMs are.