If we're skipping 2D gaming for the moment (can't forever, though), many 64 and PS1 classics would be appropriate, and would not be difficult to aquire if any of you had a Wii and/or a PS3 with their downloadable classics.
Super Mario 64 starts off fairly easy because it was the first real 3D platformer, and even Shigeru Miyamoto and his team were aware that not even many full-on gamers had played in full 3d before, so it gets harder at just the right curve for a a beginner. If you do go back to 2D, some SNES classics like Super Metroid, which is actually a very easy game with all the eventual powerups, Super Mario World, and others will do good (as she gets better, give her harder games, like the Megaman X series).
Back to 3D, allow her to play other classics, like Spyro, Crash, and OoT. Basically, if we can think nostalgically about it, it's probably a good choice, and when she's achieved a proper amount of skill to start humiliating her, break her soul forver by making her play Touhou, a doujin PC title.
Wait, that's a horrible idea. Ignore that last part (though, if she gets really into vertical scrolling schmups, than go play Touhou, as it is a great game series).