Man, seeing these replies is really starting to make me fell old

. Oh well, I always said I'd still be gaming when I was an old man, looks like I'm well on the way

.
I have a lot of game systems, both retro and current gen. I'd say my oldest daughter was about 3 years old before she started showing anything more than a passing interest in gaming, but even then, she would loose interest within 15 - 20 minutes. I now have 2 kids, (both girls, 8 and 5 years old), who are now both firmly into games.
Once I could see that they were both very interested in gaming, I let them start to play on my consoles, but very quickly found that some were way better than others. Like one of other posters, I also thought that N64 would be the sure fire best bet, but found that they both had serious trouble with the controller, that thumb stick just doesn't work for them. I also found that even the eldest child, had too many control issues with 3D games, (ie most of the N64 range that are worth playing) and ended up getting frustrated instead of having fun.
Next was the Dreamcast, and they did find the controller much easier to come to terms with, but for my youngest it was still a bit too big for her to hold properly. Also the rising complexity of the games made accessability an issue. Also as mentioned is the concern of the media being too easy to damage. Even though I would only let them use my backups, and none of my original games, I still found it frustrating to have to check them constantly, and reburn them if needed. Really the only game they both play on the DC regularly now is Soul Calibur, so the search went on.
Then when I saw them showing a LOT of interest one day in the Mega Drive, (Genesis for all the Us folks), then I really know I was onto a winner. The controller was much better shaped and designed for kids, and my eldest had it mastered in minutes. Even better was when the youngest proved that she could start playing without me helping at all. The amount of games that is available is stunning, and 95% were made for kids. Well that really goes without saying, as those of us old enough to have kids now, were kids when it came out. Really the number of adults who were playing video games as a serious hobby back in the 90's were clearly in the minority.
Even though I was very happy to have found a system that really suited them, I was worried that they would loose interest, because of the obvious graphical difference. My kids have grown up around games, and are used to seeing what is possible with current gen systems, (ie. Xbox360, high end gaming PC), and I thought that the eldest especially would quickly loose interest.
However when I quizzed her about this, she looked at me very matter of factly and said, "I don't care, these ones are just as much fun, and I can play the games by myself". There it was, from the mouth of babes, as they say.
So I then bought a second Genesis for them to keep in their play room, and almost a year later they are still playing it regularly. Even better, all that was old is new again. When the TMNT came out on every current platform, the kids naturally started to ask about playing it. Simple, I just put the TMNT:The Hyperstone Heist onto my Flash Cart, and they loved it. They are now saving their pocket money to be able to buy their own copy

.
So my reccomendation, is start them on the classics, either the Genesis or the SNES, and just let them graduate up the console ladder as they get older and more proficient. Only now has the eldest started to really push for another console, and surprisingly it is the PS2, (not the DC as I had hoped), the reason is obvious; the large amount of girl tailored content, of course releasing a pink coloured one sealed the deal in her mind. So this christmas, that is what she'll get.