Interesting to read about your kids playing the New Adventure Island Esteban. I think for younger gamers its not an ideal game. It starts out relatively difficult and fast without much time to get adjusted to the controls and gameplay, that leads to a quick frustration. It doesn't have that in-built tutorial like Mario games in their first levels.
I would try Bonk with them, or the later Adventure Island games on Famicom (but not the first one!)
Yup, exactly, totally frustrating, but guess what? My daughter loves R-TYPE (she can’t make it far) and my son loves Mr. Heli (he gets further than I thought possible, but that’s not saying much).
Yes, they enjoy Bonk (1-3), Pac Land, Bomberman (all), Double Dragon II, Hanii on the Road, etc. (totally random stuff).
My first AI was, of course NES AI (they haven’t seen that yet, but they do like a lot of NES games).