Games With Genuinely Challenging Puzzles

[Stark]

Solomon's Key on NES, I think might fit your criteria. Gets tough pretty early. Always loved that game.
The Lost Vikings on SNES & Genesis, I thought was pretty challenging too.

Ooh Solomon's Key is awesome! Add Shadowgate for the NES to dang hard.

[Gamerforlife]

-Braid - Some of the solutions require some real outside the box thinking
-Crush (PSP) - Particularly when you're trying to get everything in a level
-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
-FF XIII-2's Hands of time clock puzzles - They would progress in difficulty until you ended up with some really tricky ones. They were the hardest of all the puzzles in the game
Dodogo! Challenge - It's essentially a hard mode for people who have completed Dodogo! I need to go back and finish that some time.

[Txai]

Guru Logic Champ for GBA might be easy at first. But it gets really, really tough as you progress.

[alienjesus]

Catrap for the Game Boy can get pretty challenging. It has a nice rewind function for if you screw up, but it's still incredibly tough later on. It's also on 3DS Virtual Console.

Speaking of 3DS, Pullblox (Pushmo) and Fallblox (Crashmo) on 3DS e-Shop can be real stumpers too.

Zack & Wiki for Wii has some real challenging levels later on too.

I personally can't stand it, but you might find you'll get some mileage out of Wrecking Crew on NES aswell.

[Retronomy]

As much as I love the Myst series, I wouldn't call the puzzles 'challenging.' More on the order of "I have no freaking clue why this button did that but alright, lets move forward." Some of the logic is so foreign in those games.

[SamuraiMegas]

Portal.

[chupon]

NES - adventures of lolo
NES - lolo 2

[Menegrothx]

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 Master
Morrowind 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.

-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.

[TEKTORO]

Catherine, you are the puzzle. Meaning when you win or lose, it was all because of your decisions and path choices. Making it through most of the puzzles will take a few tries, but its so rewarding when you finally make it.