With my boy, his first significant game experience was with the original Super Mario Bros. He was a 2 year old. It took a lot of coaching to help him figure out how to move/jump. It was a really proud moment when he first killed that first goomba. Now he can beat that first level no problem. He’ll be 4 next week.
You kind of have to play with what keeps them interested too. Tiny Toon Adventures is pretty popular. Also stuff like Rad Racer and Mario Kart. I find you can’t force too much or they lose interest almost immediately. The NES is nice because the controls are simple for little ones to work and the controller is a good size.