I'd go for sceptile! Green theme! XD I did actually have gardevoir and flygon aswell as sceptile to have a themed emerald...But I also like Marshtomp because surfs helpful, as is his type combo against early leader Wattson.
this should *probably* go into the recent happenings thread, but i'll let a mod deal with that. i think you should start with Mudkip, it's great for the first few gyms, but that's if you want an easy begining. oh well, i like it anyway!
I like Blaziken so I'd choose Torchic. If you train it good enough it can take out the first 3 gym leaders by itself. It also helps against Sydney later on.
I reccomed Treecko. You will make Roxanne Juan and Wallace cry. However Swampert will be the best for the BF.
They are all absolutley fantastic though. And you can catch Ralts before Petalburg.
You should pick Treeko as your starter. Mainly because by the time you get to the Fire trainers (Team Magma,Flannery) you should already be at a pretty high level, and have time to train a water pokemon before you get to them.