In DPPt I'm pretty sure it was either Starly or Shinx, as they appear very early on, and are Pokemon that looks like some I'd want to catch, but probably Starly since it's a bird. Not a bad choice either, considering it's by far the strongest of the starter birds and most bird Pokemon in general.
I may not have played the games, but I can already predict that the first Pokemon I'm going to catch once I get my hands on the games is a Pidgey. Starter birds ftw!