Lots of good ideas circling around this tread, yes... veeery good [/creepy voice]
The idea of being able to choose which pokemon you send out first is intruguing. It could have many excellent uses like getting the pokemon you are training out right away or sending out a pokemon of a super-effective type for certain battles, as was mentioned before. However, it is true that this would get annoying in wild battles, and the whole wi-fi discussion is certainly valid, considering that the second person would most certainly be given the advantage... Finally I could send out my roleplay-knowing sableye when I see that my sister's first pokemon is her shedinja >:3. Either way, I find this idea, however debatable, a good one.
On a side note, I personally think that we need an alternate evolution for buneary, because I am still exceedingly disturbed by the horror known as a male lopunny.