if they're competitive and you have a Wii, then mario kart and smash brothers.
If they're not as competitive, then you could get Super Mario Bros Wii and earnestly try to help eachother rather then hinder.
As for single player games, it's important to introduce those as well. You need to show them that gaming can be something that they'll enjoy when you're not around to play with them. I totally understand wanting to play with them and coach them, but gaming is largely a single player experience and it's important that they wet their toes on that experience as well.
Suggestions.. JRPGs are good stepping stones into gaming. They typically have simple gameplay controls that basically come down to a math problem: Do your levels > their levels? If so, you win. So Gain levels. There is almost nothing in JRPGs that you can't grind through to make an easy experience, and if they're into anime, they'll appreciate the stories and the characters.
MMOs, like WoW.. If your other half enjoys setting out on a difficult task and the mental rewards for achieving that task, then they will probably like MMOs. They generally have a smooth learning curve, making them easy enough for new gamers to play, and the social aspect, and making friends with their guildmates etc. introduces an ARG/Metagame aspect to the game that they won't find elsewhere. Be aware though, If you introduce them to MMOs and they DO stick, then be prepared to lose them for several hours a night.
New gamers don't tend to like shooters on the consoles (controlling the camera is a complicated act that most gamers take for granted), but they can be easy to play on the computer if they are used to using that, as it's basically just point and click. Vertigo can be an issue with new gamers playing shooters though, where their mind will lose track of which way is up and down. Probably a good 3rd or 4th game if they like weapons.
Fighting games.. Most fighting games can accommodate button-mashing, so they're good for using to teach controller skills to new players. They're also generally simple in terms of movement - one stick, 2d movement plane. There's a simple to discern goal - use your character to lower the other character's health to zero.. And most of the time, they're beautiful looking games. If teaching a significant other how to play fighting games, make sure to throw any flashy combos or super moves into the mix so that they will ask how to do them, then you can teach them. Also, use the handicap system, that's what it's there for. Every fighting game has one, where one player will start with less health. If your other half doesn't like the idea of fighting you crippled, explain to them that the alternative is that you manually cripple your gameplay in order for them to succeed and get better. The Handicaps are a much better solution when dealing with a new gamer. When I taught my sister how to play Soul Calibre, I was often set to 1-hit death.. try and keep the win/loss ratio about even using handicaps, or else one of you will get very bored and quit.
Western RPGs.. As much as gamers love these, they're not that great for new gamers.. they tend to be open world, which scare new gamers. They also sometimes have complicated leveling systems, and subsystems working behind the scene such as enemy leveling that they might not understand.
On a similar note, sandbox games can be great for teaching gaming skills to new gamers. Games like Grand Theft Auto or Saint's Row, where you can basically have as much fun just living in the world, crashing cars, as you can following the story. This gives the new player the ability to play the game without any real consequence for failing. Once the player is accustomed to the controls of the game they can choose to do the story missions. If it's a girl, I would suggest Saint's Row over GTA or the new Godfather game, as you can create a female persona in that game, rather then being stuck with a male persona which the new female gamer may have trouble relating with.
Female gamers are instinctively drawn to the Sims. It's a game they've been playing since they were little girls, so it's something that comes naturally to them. I won't say much more about it because it's well documented gamergrrl'n faire, but the consoles versions of the sims, such as the PS2 game Sims Bustin' Out can provide a more "game" like experience, with specific goals to perform, so if you feel the new gamer might appreciate more structure in their game and less freedom to do wtf they want to do (although all of the freedom staples are present in the console versions, they just have a storyline roughly shoved into the mix). Sims 3 for the PC also provides a directed experience with the motivation system. Animal Crossing can also fit in here, but it offers more interesting characters for a less realistic setting and a persistent gameworld. Spore also fits here, and best of all, Spore is an EXCELLENT gateway game. Do they enjoy the Cell Stage? There are LOTS of casual games with the same sort of gameplay. Creature? Try an MMO. Tribal? try an RTS. Civilization? Try.. uhh.. Civilization. Space? Try.. Well, Spore.. nothing is quite as vast, deep, and downright boring as the space stage in Spore.
Sports games.. Only really for the sports fan, but if they are, they may LOVE to play the video game equivalent.
God of War/DMC type games.. These can be good for new players as they provide a lot of spectacle without having to rely on overcomplicated controls. Throw it on the easiest setting so that they won't get frustrated and let them go nuts. If they're a bit prudish, might want to lay off the Dante's Inferno/God of War.
