I don't own a game console, but I have probably played every adventure game available for PC, so my list is heavily weighted towards those. I'm looking forward to seeing what others like/recommend.
Myst: http://www.cyanworlds.com/products/ (old school, but I worked on the original Myst and still have a soft spot for it). I liked the exploration and puzzle-solving aspects; think it could be updated to be collaborative and with more real-world-type puzzles (fitting cargo on a ship, identifying ports from old-style maps, etc.). Not sure how it would be 'graded.'