I really like the games from Wadjet Eye Games, especially Gemini Rue, Resonance and Primordia. All of them have interesting stories and good puzzles. The puzzles are mostly very logical (but not necessarily very simple) unlike puzzles of some other adventure games.

Since you mentioned The Longest Journey, I was about to recommend the successors to that game (Dreamfall and Dreamfall Chapters), both of which have a fascinating story, but they don't really fit in the classic point-and-click genre.

Legend of Kyrandia? The second one, "Hand of Fate" , is excellent and I'd totally recommend it. The game really improved on all of the first one's problems and tells a really good, often very funny story.
However, I have major difficulties getting into "Malcolm's Revenge". That one is just weird all around and even walkthroughs for it are terribly confusing.

That was it.. anyway in the first one.. fucking fireberries or what ever how annoying that can get.. It seemed that a lot. =P

The Journeyman Project trilogy. One of my favorites. Science fiction & time travel. Need I say more? Ok, it also has some humor in it.

God, yes. That was the worst part of that game. Although it does get a lot easier once you realize that you can simply drop those stupid berries on the floor and the rooms in question will stay lit forever. Still immensely tedious, but a lot less infuriating.
Thankfully, part 2 doesn't have any mazes like that in it.

By the way, since all three of them popped up as daily deals in the Fall Sale, with a 75% discount, there's a good chance you can pick up 2 and 3 if those deals go into repeat.

Not my most played genre.

I did finish Teenagent, which is free here. My thoughts:
http://www.gog.com/forum/general/so_i_finished_teenagent

Did I once in those year was even close to finishing it? Still I would like to try second one and third.

In an amusing coincidence, I was just thinking about that game as I clicked on this topic. I remember it fondly, though I'm not sure why - I never got very far, and it doesn't seem like it was very interesting. I guess it's nostalgia then.


Anyway, instead of reiterating what has already been mentioned, I'll throw in Lost in Time. It was made by Coktel (probably best known for Gobliiins) and published by Sierra. I played it when I was pretty young, and so I never got very far (a common thread for most of the adventure games I played in that period), though I did remember the exact location where I got stuck, as well as the solutions for the previous puzzles. This made it much smoother when I (re)played it a few years ago, to completion and to my own surprise.

Oh, and how about unreleased stuff? Here's some [url=https://en.wikipedia.org/wiki/Warcraft_Adventures:_Lord_of_the_Clans]Warcraft[/url] for you.

A mix of nostalgia and the fact that it's a nice little gem from the 90s adventure scene.