If you're not both big gamers, I agree that Mario Galaxy is great.
If you're both control freaks, it might not work. It can get a little frustrating for player 2; you can really only collect stars and freeze enemies, and occassionally help high jump (both press A at once) or shoot star bits at the rare obstacle affected by them. You have no control over movement, and although you can make Mario jump and spin normally, I can't imagine that would actually help player 1.
But for us it is perfect - I don't generally play games while alone and this is just the right level of involvement for me.