Impossible to decide. Really more based on the region.
Johto- Cyndaquil(60%) or Totodile(40%)
Hoenn- Treecko(40%), Torchic(40%) or Mudkip(20%)
Sinnoh- Piplup, probably.
Unova- Oshawott. Maybe Snivy. Never Tepig.
I almost always choose the fire Pokemon. I'll list the starters according to region favorite to least favorite (Not favorite to least favorite region, favorite to least favorite Pokemon in each region).
Kanto - Charizard (5/5), Venusaur (4.9/5), Blastoise (4.8/5)
Johto - Typhlosion (4.8/5), Feraligator (4.6/5), Meganium (4.1/5)
Hoenn - Sceptile (4.8), Blaziken (4.6/5), Swampert (4.5/5)
Sinnoh - Infernape (5/5), Torterra (4.4/5), Empoleon (4/5)
Unova - Samurott (4.7/5), Emboar (4.3/5), Servine (4/5)
Water types are amazing starters! They have a type advantage over the Fire starters and can easily learn Ice type moves for the Grass starters. Water types also happen to be the balance between the starters in stats. Well-rounded is the best to go. Plus, ever since the original Pokemon games, there has been a Dragon specialty, which are to Ice types, so it works out for the Water starters perfectly. Also, the Water starters happen to be adorable (I'm talking about you Oshawott and Piplup! ), so I can't resist their cuteness! Water starters for the win!
It depends on how cool the pokemon are that are the starters and their evolutions. But, if I chose by rule of thumb, I would chose water because it destroys the fire type, and in actuallity, isn't all that weak when comparing everything of grass starters to water starters.