I've said this many a time, but make items that eventually negate the need for HMs.
That is, save up enough Pokedollars, or whatever, and you can buy, say, a hatchet, that means you don't need Cut anymore. That way you still have the HM in desperate situations but when you can afford it, just buy the item to replace it and it can just be a key item, rather than having HM slaves. Also it gives an actual use of the stockpiles of money your character saves up all game.
I support this, one of the biggest things that bug me with Pearl/Diamond is that you need so many damn HMs to get through it, Defog, Strength, Fly, Cut, Surf, Waterfall. Ruby and Sapphire too with all those damn water HMs, Surf, Waterfall, Dive, and in the Victory Road there's the need for Rock Smash, Flash and Strength too. If not give us items to replace them, then just make them able to be overwritten without the need for a move deleter, never really understood why it needed to have such consequences to teach your Pokémon a HM. They've gotten better at it with 5th Gen, it's a step forward for sure, now they just need to go all the way.
Then there's of course the no brainer things like multiple save files, being able to go your own way in the story, etc. A thing I'd like to see in the story is a rival who is actually an enemy of yours again, like with Gen I and II, doesn't feel like the person actually is your rival when he's just your friend. I wanted to kick my rival's butt in Red and Gold, that's hard to want to when your rival is actually your friend (though I have admittedly found the rival in Pearl and Black 2 very obnoxious).