... which three Pokémon would you pick? Would you stick to the traditional fire, water, grass trio or would you experiment with new type options? How about the typical three-stage evolution? If you have reasons for your choices, be sure to add them too! I think it would be interesting to have the starters all be of the same type, fitting in with the environment of the region at hand. Normal type starters would be interesting since they aren't super effective against other 'mons--it would be an interesting challenge at the beginning of the game! Igglybuff/Porygon/Whismur as an example! I doubt it would be very popular though!
I would love to see some later game randoms pop in as your starter to mix things up. A cool combo could be like- Barboach/Shuppet/Swablu or something of that sort.
Maybe have one universal kind of Pokémon and then give it a Leaf/Fire/Water stone when it reaches a certain level and you can pick which way you want it to go. This way, the starter will be similarly designed, but have its evolutions, stats, movesets and typings vastly different.
If I was going with traditional Fire/Water/Grass, I'd have Torchic/Piplup/Rowlet, because birds are the best. For something not so traditional...I dunno, maybe Pokémon that don't evolve as early as the starters, or have a slow EXP growth rate, to at least attempt to facilitate some sort of challenge? Deino/Gible/Bagon would be pretty interesting! Or for a more traditional triangle, maybe Psychic/Dark/Fighting. For Gen V in particular it would have been cool if they'd deviated from the normal and gave you a choice of Solosis/Gothita (depending on your version), Sandile, and Timburr. Or Sandile, Litwick, and Sewaddle even, that seems a teensy bit more balanced type-wise. Giving us a single Pokémon that doesn't evolve would be fun, especially if they had Mega Evolutions to compensate for that. Maybe Heracross, Mawile, and Aerodactyl?
A nice triangle of typing is Steel/Ground/Ice. I feel like these always work nicely, so no harm in them.
Pokémon is actually kind if weird for giving a choice so early on. It would make more sense maybe to have you start off with a set Pokémon, which can then evolve into something of your choosing later on. Eevee's kind of perfect for that, actually. I wouldn't mind there being a smiliar Pokémon, but which only evolves into a fire, water, or grass type and depending on some factors other than evolution stones. Like if there was more of a roleplay element to the games where you can choose dialogue options, like in Mass Effect or something, what it evolves into would be tailored to your personality.
I'd go for some other triad, like Ghost/Dark/Psychic (even though Ghost would be really weird to have at the beginning with Normal types and all)