Here's my wishlist:
I agree with RedCrow on faster battles--VERY necessary.
Also better "throwing Pokeball" animation would be cool.
Get rid of Pokemon animations, god those are irritating
HP bars that don't take hours to drain (Blissey is hell)
Being able to actually view EVs and IVs instead of constantly calculating them
A Battle Tower that limits Hax moves and items
More interesting type combinations like Ghost/Fire, Fire/Grass, Bug/Dragon, etc. There are tons of combos that have been unused.
More evolutions of current Pokemon, like how we got in DP. Those are my favorites, and useful for bringing some Pokemon up to OU battling
Being able to Fly in the air and come across areas/Pokemon in the sky (like Dive in R/S)
More alternate battle music. Like a different battle theme for in a cave, in grass, in Safari Zone, at night, in Battle Tower, etc.
3D battles, oh wait, too late haha
MORE CHALLENGING in general: Trainers should get up to level 60s before E4, and it should be more difficult to earn money