Baldur's Gate Dark Alliance 1 and 2, Champions of Norrath 1 and 2 and Some D&D game on the XBox were games my girlfriend and I enjoyed playing.
Harvest moon might also be a nice little game, although you can't really play cooperatively.
Have you tried the Zelda series? Especially in some of the tricky dungeons, we had loads of fun trying to figure out the puzzles together...