When I pick a starter, I choose one with a type that would be hard to capture in the wild. Say, for example, I'm playing Emerald. I usually go with Treecko because grass types that don't suck are hard to come by in the wild. I believe only Oddish, Lotad and Seedot are around in the beginning, and they suck imo. Tropius is cool, but it doesn't appear until later in the game. The only gen 3 grass type I like is Roselia, which isn't available in the wild in Emerald.
But anyway, when I'm done picking my starter, I try to find a non-water type that can learn Surf, because I don't want to cram both Surf and Waterfall into one Pokemon's move list (or in gen 2's case, Surf, Waterfall, and Whirlpool; in gen 3, Surf, Waterfall, and Dive).
When I'm done with catching Pokemon that have covered the Grass/Fire/Water range, I look for a Pokemon that can fly and another that can use dig. If I'm lucky, someone in the Grass/Fire/Water range can learn dig, but I don't like to teach my starters too many HM/Field moves.
Anyway, after that I look for Pokemon with type variety that I don't yet have in my party.
I couldn't care less about stats and nature.