Hard time deciding between Charmander and Mudkip, but I'm choosing Charmander because it was my PMD character, and Charizard is one of my favorite pokemon. The downside with Charmander is that the first two gym battles can be hard.
In fact, for the R/B(Yellow doesn't count, since your starter is always Pikachu) and G/S/C generations, I preferred the fire starters, but for R/S/E and D/P generations, well, I don't care for chickens or monkeys, so I went with the water starters. "I liek Mudkips" -ahem- and I like penguins. Although, I started with Treecko once because the egg type or whatever was dragon