Spycraft: The Great Game - A large variety of things to do as you solve a mystery. What's great about it is that it requires a good bit of deduction work to piece things together, so that puzzles aren't simply trial and error.
Normality - A neat mix of point-and-click adventure game with FPS-style movement in a colorful 2.5D environment and with a quirky sense of humor.
Realms of the Haunting - Uses the same engine as Normality, except that there is combat. It's got a good number of unique puzzles across diverse locations and an interesting story.
The Kyrandia games:
Legend of Kyrandia - Classic style point-and-click game, but there's one large, somewhat obnoxious maze, and there's numerous points where your character can be killed.
Legend of Kyrandia: Hand of Fate - I feel like this is the most solid entry in the trilogy. Plenty of puzzles, interesting characters and settings, it just feels more solidly designed than the first entry.
Legend of Kyrandia: Malcolm's Revenge - The game's hand-drawn backgrounds and characters are replaced with early 3D pre-rendered art, but it has it's share of quirky puzzles and settings.
Inherit the Earth - Features an interesting setting, but it's light on puzzles, and the large isometric maps feel fairly empty. But still, the game has its charms.