I'd like to see Pokéballs replaced by ApriBalls. Players have to collect the Apricorns themselves and hand them over to craftspeople who make them into Balls for a fee.
The ApriBalls have different functions and aren't differentiated by power (so Fast Ball, Lure Ball instead of Great Ball, Ultra Ball).
This Fan game element should take place in a Poképast.
I almost agree with DOA_Hitomi, but would take it further; remove HMs and implement Key Skills that the player picks up over the game, some of which are only usable with a compatible Pokémon in the team (Teleport, Fly). Players get the Skills from Skill Tutors. And I'd remove TMs entirely and replace them with Move Tutors that cover áll teachable moves (for a price).
Multiple regions are needless, raising the level cap is unnecessary and would be more hassle than its worth. Even two regions is too much for most stories, simply fleshing out a single region enough will do a much better job of providing a fun experience with a proper flow.