Two votes Charmander. I don't care if it is overdone; it's overdone because Charmander are awesome!
Name: Bren if male, Claire if female. Personality remains the same for either gender. Fairly sarcastic (think Memetic but less annoying) and distrustful of humans. Also a pyromaniac. Grows more trustful of Melinda over the course of the journey. Also blends hir personality to be more like Melinda's over time. (I read someone say that your starter should reflect your character, and have loved the idea ever since.)