Overall I'd like to see some fairly major changes to the game overall, whilst still keeping somewhat the core reason of why you play it the same.
1. HMs. Fuck them. I agree with the move pool suggestion from above; All Pokemon should remember every move they can perform, however you have limited slots for moves to use in combat. Additionally, certain moves have upgraded versions - aforementioned scratch to slash - that are literally just a better version of the move, that simply replaces the old move rather than having a cluttered list of redundant moves. I mean, who uses ember once they have flamethrower?
And on that note, get to the awesome moves a little faster. I remember playing Ruby & Sapphire, and waiting until nearly the very end of the game before one of my pokemon could use something like flamethrower that was cool. Ok, maybe not right before the end, but certainly after midway, after the final evolution of my starter. Maybe I didn't look up every pokemon that had flamethrower and found the quickest way to acquire it, but I shouldn't have to. Awesome moves should be unlocked constantly, rather than Ember, slash, more growl, different growl, smokescreen, different slash, useless move 7, ect. And then flamethrower. I'm not saying give out the most powerful moves at the start, but there is a period where about the only change to most pokemon is its stats when it levels up, and most of the moves are redundant. I'd like to see constant improvements that actually engage me, more than make me question WTF I'd want that move for.
2. I like the idea of a more open world progression, and the option to pursue either the story, or the gyms, however it would have to be carefully crafted. They did a similar concept in Legend of Zelda; Link Between Worlds and... I hated it. I never felt like I was actually progressing, rarely unlocked something cool or new, and overall just seemed to detract from the game, rather than add to it. Naturally, gym leaders need to scale to the number of badges you have. The trainers on the paths you find also should - and should have semi-randomised parties. Gym leaders? Mostly fixed parties, but those trainers are really boring when you know exactly which pokemon they'll have on your second playthrough, and this is a better use of randomness than a procedural pokemon catch placement IMO - that just removes the awesomeness of some pokemon, when really rare or cool ones can appear right at the starting area and everyone farms them to catch early on, and kind of detracts from the feel of each area, but more on that later. There should also be small bits of a few continuous dungeons that you can't do without the HM and gym badge, like the Elite 4 areas, that guide you to a certain order of doing things, don't force it, and that give you some small semblance of progression from still unlocking things with each gym. IMO story content should not scale its difficulty; Hard encounters are hard. This fits more with the feel of the story, and can be used to guide players to play more in a certain sequence, whilst making them feel like its mostly their choice - they want to train up and get stronger before taking on those really tough but not unbeatable story areas.
3. Pokemon encounter system needs to change. Lots more pokemon in each area. 10-15 rather than 3-5. You've got enough generations now to do this. Additionally, areas should be larger. Not a ton more open, that just leads people to getting lost and kind of clashes with the semi dungeon-crawl experience pokemon has always had, but larger. I shouldn't be able to just run through the area in 30 seconds, it should be a significant area, filled with interesting content.
Additionally, allow the player to purchase various bait items. I don't know anyone who enjoys running in a circle 500 times to try and get that rare pokemon that only appears in this area. Have various qualities and types of bait. Lower qualities attract the less rare pokemon, and different types of bait attract and repulse different types of pokemon. This way the player has to have some idea of what pokemon are likely to be in the area, and choose the appropriate bait, and the quality they want, to catch them. Bait quality is not restricting on being able to catch lesser pokemon - if there's no rare pokemon in an area, high quality bait will still attract the lower rarity pokemon. Types however shouldn't work like this, and fire bait will not attract water pokemon and such. This teaches both the typing and counter system, as well as lets the player discover and think about the world itself, and removes the needless grind of running in circles, allowing players more certainty in their encounters - for a hefty price that's only really reasonable if you're post end-game and filling out your pokedex, though can be gained slower outside of this.
4. Battles. Its a tough one. The formula is tried and true, however very basic, very simple, and not very engaging anymore. For one, there needs to be animations of the pokemon kind of fighting or such even when you're not making moves; quick enemies should dart around their opponents, tougher, slower enemies should get in defensive positions, and all sorts of such dynamics. They don't necessarily need to be attacking, but they need to be interesting to watch at least.
Secondly, I'd do away with the one by one turn sort of thing, and make it more like what people love about fighting games - the battle of timing and positioning - without the silly combo knowledge requirements. You can order your pokemon to attack at any time. As they're attacking, there is a natural window of time during the animation for the opposing pokemon to block or counter that attack. Still very much draw on the pokemon styled combat to date's strengths - the tactical requirements of typing, and each move having advantages and disadvantages in certain situations, but make it more active and reactive, as opposed to simply sitting there and spamming your most powerful move for most of the game. The same strategic thinking and typing of current pokemon battles, but with an added timing system as well.
5. More exploration in the story. This is what most of us at least originally played pokemon for. To discover this amazing world filled with cool creatures. These days, its become very formulaic. Every region has very similar areas, with maybe a tiny novel thing thrown in to say "Hey, we're hip and different", but instead all they've done is changed the look of something, and removed most of the complexity of an area that actually made it interesting to explore. The best example IMO is that stupid bridge in Black/White. No content. Just hold the forward button for a minute. "But hey, we can do curves". NO. BAD GAMEFREAK.
Focus the story on finding out more about the world again. Have some sense of mystery. Who is this team and what are they doing? Not "Oh, we're bad because we're bad", and not "Oh, we're here to turn the entire world into land" right at the start. Have them be mysterious, and leave the player asking what they're actually doing. What their goal is. And make it interesting.
Have both a rival, and a friend. Your rival will constantly show up and you'll always be questioning when and how much stronger he's gotten - like Gary in the originals, before you'd played it 20 times - and actually be a challenge that doesn't completely block your progress, but impedes it in its own way, in its own self-contained story. Or change the outcome based on how many wins/losses in a logical and intuitive way; Maybe he becomes really arrogant and strong and thinks he can beat the bad guys, but fails and you need to save him. Or he manages to get up to the big boss, because you let him get so strong, who promises him power or something in return for helping him. Or maybe he decides to join up with you in the final confrontation, because you beat him many times and he knows this is beyond his league, but together you can defeat them. That sort of thing.
Your friend on the other hand would be into exploring the world with you and finding new areas and things, and navigating them with you. And have these places actually need navigating, and be interesting to explore mechanically as well as visually.
All this should make the story side of the game much more engaging. I don't think that the Gyms/Elite IV needs to change too much, there's not really much reasonable way it could outside of very specific stories in some games, but it shouldn't be literally tied to everything else in the game like it is; have it encouraged to work on both at the same time simply to level up and get HMs that allow you to explore more effectively and such, but in general you shouldn't have to beat Team X's grunts 20 times before you can challenge the 4th gym.
6. Multi-game connectivity needs a slight revamp. Take advantage of streetpass. I hate having to find a friend who's got the game and is interested in trading. Let me instead use streetpass to help other people evolve their pokemon, and me evolve my own. And allow catching pokemon from streetpassed people's games, rather than only by buying the other game or trading to it.
Oh, and fuck event only pokemon. If you're going to do this, code it into the game, with an internet date/time check, that that event will happen every month/year or whatever is appropriate for the individual pokemon [Mew should be very, very occasionally, other rare pokemon that aren't quite as, well 'legendary' for their rareness should be more common. There should be at least one of these available every day of the year, however]. None of this event you have to go to bullshit, and have a small quest surrounding acquiring them. EXPLORATION people, not "Oh hey, here's a free legendary pokemon no-one in-character has seen before" delivery girls.
7. Finally, find a way to improve the ability to train new pokemon after the end game. Maybe give trainer battles and wild pokemon battles the same experience gain. I hated that when I got to the end game, but up to the level of the gym you just beat [As in, the level of pokemon they had, not the level of pokemon the next gym has]. I wanted to play around with some pokemon I really liked, that were low level at times, however it was near impossible to grind them up to level as the wild encounters were so slow to do so, but they'd die too quickly in trainer battles. I guess in some ways this also creates a bit of a New Game+ if you include the ability to re-challenge all the trainers and such, just without the story components [Unless you haven't beaten them yet].