I have a big thing for exploration and uncovering the whole world map (lord knows why). M&M always filled that need nicely.
The Fool's Errand is a brilliant word/image puzzle game from Cliff Johnson. It's made up of a more or less non-linear series of puzzles. Solving each of these puzzles provides a chunk of story text and adds a tile to an overall world map, which itself is a puzzle. After all of the pieces of the map are obtained, you have to figure out where each tile goes on the map. Once this is finished, there is a series of puzzles embedded in the map that you must solve with clues given in the story text. I've never seen this sort of uber-puzzle approach in any game before or since, with the exception of some adventure games. But even those never presented the puzzles in such a unique fashion. The game (and others from Mr. Johnson) are available for free download at his web site:
http://www.fools-errand.com/
You'll need to set up a Mac emulator (evaluation version and instructions given on the site) to run most of the games, but they're worth it. If you like The Fool's Errand, a sequel is coming later this year which you can pre-order on the site. Check it out.
Dan