People generally don't mind Surf or Strength, it's usually something like Cut, Rock Smash, Defog, Flash or Whirlpool that people consider annoying. I do think that with the free and widely available Move Deleter / Move Reminder we see in Gen VIII, those HMs would be less annoying though, since the real problem with them is that they have a tendency to linger on your movesets long after they've stopped being useful.
People also generally don't complain about the exploration when they're talking about HMs (although some people do complain about that), to the point that the people that complain about HMs usually like the way Alola did them, or the way some hacks do them (Key Items). You can have elaborate maps with branching structures and what not without having HMs.
And they just ... feel artificial. There's no particular reason a Meowth should need to know Cut to be able to cut things or a Pidgeot should need to know Fly to Fly somewhere.
Personally I think that an alternative to the HM system that is tonally consistent with the series would be to go for a Rangers-esque style in that any Pokémon that could conceivably do the HM can do it, although how much it can do is decided by some lore details (e.g.: Rampardos can absolutely
wreck the biggest boulders you've ever seen, while something like Rockruff can only break small rocks).
That would keep the planning aspect in some forms (although it's still a bit restrictive in that it doesn't make any team you want viable. For example, if I want to beat the game with a Wurmple, a Caterpie and a Weedle, I should be able to do so), make tonal sense, encourage catching and team rotativity in a natural way and allow for more open world exploration and many ways to solve problems (e.g.: a Pokemon might be able to fly you over a bush instead of you needing to cut it).
I also have yet to see a convincing argument why Fly shouldn't be available from the start of the game. It's just fast travel to places you've already been. More often than not doing the backtracking "by foot" is not even hard, just annoying and time consuming, and from a design perspective you should want players to be able to backtrack and explore previous areas after they figured out that hey, maybe they do want something that was around there.
Edit:
agravedigger said:
the thing with me is it makes you plan your team better - can't just have 6 dragonites.
Something I noticed is that, ironically enough, you can. In Gold / Silver and HeartGold / SoulSilver you get access to Dratini, Ditto and the Day Care at the same, just before the 3rd gym.
There are 5 necessary HMs to beat the game, of which only 1 can't be learned by Dragonite ... which is Cut and you only need to use it in one place in the entire game: Ilex Forest, to get to Goldenrod, which is where you get the Dratinis.
Even if you got a Dratini in via trading or something, you only need to catch one Oddish or Paras (both found in the forest) to get to Goldenrod and then bob's your uncle.
Similar arguments can be made to most other games if you just trade in a female Dratini early on / Time Capsule your Dratinis at an early level.
Not that it would even be as easy as you're suggesting since it takes forever to level up one Dratini let alone 6 all the way to Dragonite. You'd probably have an uphill battle most games until you beat the 8th gym or something.