Get 'em going on the good stuff. That way they won't suck when they get a little older. Started my son on Super Mario Bros and Mega Mans when he was 4 or so. He can hold his own on those games these days.
They'll never like Nintendo if you give em the weak crap that nobody likes like Fisher Price and Sesame Street. Throw on some Contra, plug in the Konami code and let em go.