Something that I think they could do to totally change things up:
8 Pokemon in party
Not like you think, so hear me out.
You'd have two extra spots in your party, I'll call them "Shadow slots". You put two pokemon in these slots. To switch pokemon in or out of them, you must either be in a pokemon center or not be in a battle (could go either way, whatever fits better. I'm not saying both of these would be allowed). Yet when someone challenges you to an 8-battle, those pokemon are avaliable for use in battle. This could work great for later, more powerful trainers.
This could also help with some of the annoyances over "HM slaves". Maybe pokemon in these slots, while not avaliable for regular battle, could still be used for their HMs. Don't want a water type on your team? Keep one in the shadow slot for surf.
And they could also have the option for an 8-battle wifi battle. Just imagine how different the game could be just by adding 2 extra pokemon. It could be a whole new thing altogether. The good thing about it would be, aside from maybe some later optional battles, it doesn't HAVE to be used, so it'd have no real effect on people who just want to play the game with 6 pokemon or stick to the regular kind of wifi battling.
Also, speaking of abilities, one more idea:
What if there was an ability allowing a pokemon to learn one extra move? Or something that would allow a pokemon to have two "move sets", which each contain a move called "set shift". This would allow the pokemon, when it uses that move, to switch over to the other set of moves and thus have 6 other moves at it's disposal.
But I prefer the first idea (the one unrelated to abilities).