Since the OP asked about puzzle solving/quest difficulty and not combat, I would say Daemon's Gate is the hardest one I've played. You start the game in a city besieged by daemons and you have to find a way to sneak out. You know that your mission in the game is to find a way to stop the deamons. And poof, that's all you know. You can go around and talk to lots of random NPCs, and they'll occasionally drop a clue as to how you can get out of the city, but there is a crucial item that you can only concieve of by being really really sharp, or, which I would wager the majority of people have to do, by stumbling on one tiny building in this miles-wide cityscape.
And that's just the start. The rest of the game follows pretty much the pattern, telling you what to do next but not how to do it. Most times in games, and most times in life, if you're way off track you have some sense of when you should stop going and turn around. Say you're headed for Seattle and you start seeing signs for CANADA. But in Daemons Gate, you don't know if you're in Canada or if you just aren't in Seattle until you find one NPC in a random bar somewhere in, again, a miles-wide city scape. Give up, or keep looking harder?