-A darker, grittier region to explore - or at least a region with gritty areas/towns. Something like what Orre was in Colosseum/XD.
-Make the "main villain organisation" seem more... evil, and dark. Don't make them just a "lolz were gonna kidnapz duh legendary pokeymanz oh no a 10 yer old boi defetud uz". And don't make them have countless Zubats.
-Make them have a darker intent than just kidnapping a legendary Pokemon and using its powers. Cipher was something unique regarding the "main villain organisation" thing as it tried to use the powers of Pokemon as a whole, creating (essentially) a new type altogether - one with a higher power than before. And make them seem like a threat for the general public - like, they're really, REALLY infamous, instead of a few random people saying "Oh, you know Team Ridiculous Name? I hear they're doing horrible stuff to Pokemon!".
-Make the "big boss" of the "main villain organisation" really freaking insane, but with a convincing intent if you look at it in a different angle. Like, seeing all humans as evil, because they force Pokemon to fight each other for nothing more than a laugh, if you think about it. But of course, he'd be a hypocrite and a mass murderer to make you soon forget about feeling guilty (which you shouldn't anyway - they're only pixels. The idea's just to add depth and darkness to the plot).
-Have the rival work for the "main villain organisation", but you don't know it at the start. So at the start, you meet him, and he just appears to be a thug and a thief, then you find out his intentions and the fact he's working for the MVO, then towards the end you find out why he's a member, and it's a sad and dark tale which makes you feel sorry for him. But really, I just don't want your rival to be your BFF who is no threat.
-Involve the politics of the region. Maybe they're a motive behind the MVO's plans? Maybe the goverment of the region is corrupt, and are semi-bad guys in their own right?
-Have more variety for the gym leaders. I don't mind having mono-type gyms like we've had for the last 4 generations, just don't let them have two/three of the same Pokemon/Pokemon that are in the same evolutionary line. I mean, there are lots of different Pokemon with different type combinations - for example, in terms of grass Pokemon, there's Grass/Poison combos, Grass/Dark, Grass/Water... yet alot of gym leaders have just plain old "Grass" Pokemon. Spice things up a bit!
-After the Elite Four, let us beat the Elite Four of the previous regions. Or maybe, let's say, if you beat the first region, then beat a previous region in general ala G/S/C (Sinnoh or Hoenn are most likely), you can go to the remaining region's Elite Fours. How does that sound?
-The "skill spot" (reserve HMs for two extra move slots which can't be used in battle) is a good idea.
-Have a kind of "Sky Fortress Machine", owned by the MVO, attack the "capital city" of the region towards the end of the game, and you have to stop it. You'd fight your rival for the last time quite early into the fortress, before he breaks down and decides to help you fight the MVO final boss. I dunno, I think it would be better and more realistic than just YOU passing through the fortress and fighting the final boss, considering your rival would know his way around it, and know any traps and stuff.
-Customised trainer clothes and stuff, please. Also, perhaps as rewards for beating the Elite Four, you could unlock previous trainers' (like Red, Gold, Ruby, etc.) clothes, and maybe even Mario's or Link's clothes (would help Nintendo promote any Mario or Zelda game out within that time).
-If you're gonna have the "normal/flying/bug" thing they do in terms of Pokemon you catch in the early routes in the beginning of the game, why not expand on that? Like you can catch a number of normal/flying/bug type Pokemon near the beginning of the game, so 1st gen fans could catch a Rattata/Pidgey/Caterpie for preference, and 3rd gen fans could catch Zigzagoone/Tailow/Wurmple for preference.
-A good, fast online service on Wi-Fi, with online gyms, tournaments, leagues, etc. all set up within a couple of button presses.