I'd like to see a ghost/normal pokemon.
Some of the earlier Gen starters as wild pokemon. I mean those pokemon have to be wild somewhere right?
Let's put the next game in that region.
After you defeat the Elite 4 and become league champion, you have to defend your title every so often against trainers you beat in the game.
I think the option of creating your own gym would be pretty kickass too.
If they could give the pokemon league more of a sports tournament type feel I would dig that. Your trainer has to battle his way up the ranks sort of modeled after college sports ranking until the final tournament.
Your Pokedex could keep stats like wins, losses, kos, critical hits landed stuff like that.
There could still be an Elite Four. Every time you reach the final tournament there are 7 elite trainers(you making up the 8th seed) who always make it so you have some idea who your going to face.
But here's where it gets awesome. The game could randonmize the seeding and the AI victories so you never battle the same Elite 4 twice.