I'd go with Treeko, definitely, he's fast and learns leaf blade, which from the start is a decently strong move and it's coupled with a high critical hit ratio. For the water type I'd also choose mudkip. Whenever it gains its ground type when it evolves makes it a pretty powerful contender.
If your talking about separate games, I'd get Torchic for R/S/E, and Squirtle in FR/LG or R/B/Y. if its HG/SS then i would get Treecko/Charmander. it makes things easier later on. trust me. i won't spoil it.
Since this is for generation IV, he has to be talking about HGSS, and he's also talking about the times when Stven and prof Oak give you a new pokémon. So I'd pick Treecko and Squirtle, Treecko is just awesome with Leaf Blade and it's super high Attack and Speed and Squirtle is fun to use and it evolves into Blastoise, which is amazing!