If its for kids who haven't developed a preference yet, start them with RPG rather than FPS. I have no idea if the preference for one over the other is nature or nurture, but it's worth a try. I personally think that FPS is worse for a person's character - both in the sense that it seems like there is worse violence in that category (eg GTA) and because it lacks the layer of separation between you and the action happening onscreen.
Mario is an easy pick, can be any age. Kings quest series and age of empires series are great too, but not for kids too young to handle strategy and puzzles. Legend of Zelda, Catan (Junior)