Silent Hill 2 on the hardest puzzle difficulty setting
The first Portal game: after you play through the game (it's a very short game), you can replay the levels with either time or limited amount of portals challenges, that force you to rethink the way you compete the levels.
Adventures of Sherlock Holmes-games
Supaplex: It's a Boulder Dash type of game. Not really a puzzle game, but the game gets really hard towards the end and you have to really carefully think of your path.
Dungeon crawlers/RPGs:
Legend of Grimrock
Dungeon MasterMorrowind has some challenging puzzles and riddles, unlike Skyrim.
Quite many oldschool RPGs (like Ultima 3) have some challenging puzzles, but fit the bill if you just want a game where you generally need to figure out things on your own with out any hand holding, not just when you're solving puzzles. And quite many of those Dungeon Master/Ultima Underworld type of 1st person view dungeon crawlers have some puzzles, but they are quite scarce so not probably worth it if you just want to solve some puzzles.
Gamerforlife wrote:-PC Adventure games in general - I can't think of many that were easy for me. I guess if I single one out it would be Monkey Island 2. That one took me some time
This. Sam and Max Hit the Road and Monkey Island 1&2 are excellent games to start with.