>>36595394HMs aren't a problem remotely on a conceptual level. People just don't like their in-game implementation of taking up a limited move slot on a useful Pokemon
If there's going to be obstacles to overcome in the game world, it SHOULD be via your own team of Pokemon. Renting Pokeubers that are random ass Pokemon that you don't personally own and sticking all out of battle functionality onto a mandatory starter are both utter shit solutions to a problem that could have been solved fairly easily.
Literally that needs to be done is relegated stuff like moving boulders, surfing, flying, going up waterfalls etc to some sort of system that isn't tied to your moveset for combat.
It should 100% be your Pokemon accomplishing these things.