Beneath a Steel Sky is good but incredibly rough, so it makes sense that it alienated someone unfamiliar with the genre. Here's what I would recommend for a newcomer:

1. Grim Fandango

This had tank controls rather than P&C until the remastered edition, but it counts now. One of the best games ever made. If you can't get into this one, the genre just might not be for you.

2. The Curse of Monkey Island (aka Monkey Island 3)

It gets crap from series fans, but it's fantastic, hilarious and very streamlined. One of my introductions to the genre.

3. Gabriel Knight: Sins of the Fathers

It's been recommended already, with good reason.

4. The Longest Journey

Another classic. Some of the best characterization I've seen in an adventure game.

5. Space Quest VI

The most playable game in the series by current standards, and really funny.

As someone who generally doesn't like Point and Clicks, I have to say, I had a good laugh at the Sam and Max games. Funny, light-hearted, with very simple coherent solutions. They feel more like exploring a story and less like "what the hell am I supposed to do with three toothpicks and a bag of popcorn?"

I got to like this genre with

Broken Sword 1
and
Maniac Mansion 2: Day of the Tentacle

Perhaps it is just you. :P
I liked the Deponia games and would recommend them. I was relativly new to point and click games (2nd point and click game in my life) and was able to finish the Deponia trilogy. Some puzzles were harder but I can`t remember any illogical puzzle.
P.S.: If all people would like the same the world would be a bad place to live.

One thing you have to understand is that a lot of the older adventure games (particularly those from Sierra Entertainment) were PURPOSEFULLY hard. If it seemed impossible, that's because the idea was to get you to buy the hint booklets which they oh-so-conveniently offered at an additional price. As the (self-professed) World's-At-Least-5th-Biggest-Connoisseur of adventure games, I HIGHLY recommend the following:

Grim Fandango, especially the remastered edition. No illogical puzzles there, and lots of humor.
The entire Myst series. These basically set the standard for adventure gaming forever, and my fondest memories are of those. Everything is logical, but not necessarily easy.
Broken Sword: The Shadow of the Templars. This one is a much more involved story than the previous two, with nifty animation and, again, logical progression. The rest of the series isn't nearly as good, sadly.
All Amanita Design games (Samorost 2, Machinarium, Botanicula, etc.). Honestly, some of them are more in the category of "interactive art" (particularly Botanicula), but they're unbelievably beautiful with clever puzzles, and, in the case of Machinarium, a built-in hint system if you get stuck.
The Sherlock Holmes series of games from Frogware Interactive. True, most of these aren't on GOG, and nearly all of them are deathly expensive, but they're well worth the money. Each story feels like it could've been written by Sir Arthur Conan Doyle himself, and the deduction system puts you in Holmes' shoes. Each is marvelous, an absolute masterpiece, and always just hard enough.
Lumino City. A true artistic masterpiece, with everything made out of lasercut paper and various lights and things. Includes an in-game hint system, so you should be fine. Only hard puzzle to speak of is the music one which requires a bit of memory and has a typo in the hint guide.

Games to avoid if you're new:
A majority of the LucasArts collection. Now, I know this is probably a very unpopular opinion, but let's face it, some of those puzzles, as you mentioned, are just downright overwhelming if you're new to the genre. Possibly the nastiest of which I recall being in the first Monkey Island game, where you had to step on a board that there was no indication you'd have to be on in order to lift the plank and scare a bird away from a fish. While these are some of the best-loved games out there, I advise you get more experience before trying them out.
WadjetEye games. Again, I'm probably gonna get hate for this, but a number of these focus on pixel hunting, which you said you hate. They're mainly known for their strong stories, but that's no good if it won't keep you entertained.
The Sierra games. Do NOT, I repeat, do NOT attempt a Sierra game if you hate puzzles. As I've said before, they were purposefully mind-numbingly difficult, and you would die if you did so much as sneeze at the wrong spot.
The Gabriel Knight series. It's rather complicated, unless, as I said, you're already familiar with the genre.
The MacVenture series. Don't. Just don't. Don't do that to yourself. Nobody deserves that level of difficulty.
The Gobliiins games. The logic is mind-bogglingly confusing and cartoonish. You have to learn to understand how their world works.

Somewhere in the middle:
The Adventure Company games. While this is my favorite company, their games are a mixed bag. I personally love all of 'em, but I just love adventure games. The look, feel, and gameplay might feel outdated and boring. If you like Myst, you might like these games. If you didn't, you might not.
The Daedalic games. Emphasis is usually on stories, and they usually all have a very nice art style. However, the games are pretty wildly different from each other, so it depends on what genre you like.
TeenAgent. Really, it's not that bad, but there's no clear sense of direction for most of it.

Really, there's no shame in looking up a walkthrough if it's just that difficult. Yes, a huge part of the adventure game experience is solving it for yourself, but let's be honest here, if you're stuck on one puzzle for 3 days and aren't progressing, are you having fun? The whole point of the game is to enjoy yourself, so do it!

Yes, I listed way too many. No, I don't care.

where's awalterj on this? maybe he's writing a huge wall for us all and it's impending...

Anyway. I totally understand where you are coming from, there are tons of different types of P&C adventure games and finding the right games with the right flavors to suit you could take some misses and be disconcerting. It sounds like we might have similar tastes so hopefully I can be helpful.

The puzzles almost always have to be practical-application/inventory-to-world-interaction logical types (I like to call them MacGuyver-types sometimes.) I don't like "mini-games" that take you out of the game/don't make sense to really exist in the world of the game or convoluted symbol-figuring out and weird machine operating type stuff, which sounds about the same as you.

I like them to be mature or sophisticated in certain ways (don't misunderstand this to mean sex and violence or super-brainy either. Like with the Monkey Island games, I was never able to get into them because they were too juvenile. Some games are fine for kids, but are still mature/sophisticated even, like The Dig.)

But supreme above anything else in a P&C adventure game for me is the story. I think it is the type of game best serving of good stories and story-telling and I pretty much view them as interactive novels and if the story is lame, I'm almost most definitely not going to like it. With that, I often find the stories in computer games will often be good-great, but the writing, voice acting, or just some sort of the presentation in general (even the UI) can come off a little rough and not be done superbly. I find this especially true for P&C adventures and find often to really be able to appreciate them for their greatnesses, you have to forgive some shortcomings.

Here's my breakdown of favorite P&C adventures and why they might be good for you:

The Longest Journey - The best of the best for all of what I said above, imo. It has a long, deep, mature, sci-fi/fantasy story that has it all. Don't read too much about it, just play it. However, it might not get better than this, so, don't hold it as a comparison and allow it to take away from the enjoyment of other very good games because they're not as good. Who knows, you might not find it that great, especially now that I've hyped it up! It's definitely not for everyone, I suppose.

Gabriel Knight - To me, the 1st one is good to play first, but isn't riveting or great, it is just good. It is easy, has tons of dialogue and mostly easy "puzzles," and is a great introduction to the characters and lore/world of GK, but, it's not absolutely going to sell you on loving P&C adventure games either, probably. What it will do is set you up for Gabriel Knight 2, which to me, is one of my favorite P&C adventures ever. GK1 isn't necessary to it, but enhances it quite a bit and may make it even more enjoyable. Even more bonus to you possibly liking GK2 if you like Germany or Werewolf tales. GK2 can get a bit hard at times, but, it is all logical (except for 1 puzzle towards the end which just takes some luck/timing) and great great gameplay, story, and atmosphere. GAH, every time I think about it I want to play it! Oh, and, GK1 is voodoo. GK3 is a bit of a mix, but is heavy on The Knights Templar, takes place in France, and is overall very very good. It's also got some harder puzzles, but they are good and the story is good.

Full Throttle - It's not here yet but maybe they'll give it to us for the holiday season. I personally won't endorse/recommend a remaster, but, as far as the original. I LOVE IT. It's relatively short, but it is top-notch all around. Story, atmosphere, music, voice acting, and gameplay. If you ever wanted to be a bad-ass biker, play this game! If you want to like P&C adventures, play this game! I don't know what is not to like about it, honestly.

I've also played and recommend: The Dig, Day of the Tentacle, Sam and Max Hit the Road, and Indiana Jones and the Fate of Atlantis, but Full Throttle is my favorite that I've played of the LA adventures (I've not played LOOM, didn't care to play the Monkey Island games after trying a demo way back.)

Rex Nebular and the Cosmic Gender Bender - This one has a bit of naughty-humor to it that probably appeals to teenage boys, BUT, it is also very aware of itself, is actually anti-chauvinistic, and works as social commentary to a large degree. It's cheesy, it's B-quality in many ways, but it's still great. Interesting story and world, great puzzles, a million fun ways to die, and, I think it's an absolute classic that deserves more love.

Others you might want to check out but I haven't completed/played yet:

Stasis, Primordia, Technobabylon, Pathologic (hard and not exactly P&C adventure, but, cerebral, mature, dark, awesome.)

Wait a little while. Double Fine announced a week ago that they're doing a remake of it, and, like the special edition of Secret of Monkey Island, you'll be able to swap back and forth between the original and the remastered edition freely, so you're essentially getting both with one purchase. When that comes out sometime in 2017, GOG will probably get it.

I'll keep it short:
Here's another voucher for the Syberia series.

Uhm... and Grim Fandango and The Longest Journey and Broken Sword and ...

While far from having played "all" adventures, I have played my share and graphical adventures were my favorite kind of game as a kid. I have my opinions on a handful of titles, many of which have been mentioned here, and a few of which I differ in from what most people here say.

First of all, do NOT go for Chains of Satinav. It's not because it isn't a good game, it is actually great, but its engine is poorly coded and as a result you'll have hiccups whenever you change scenarios or move from a place to another. If adventure games test your patience already as they are, this one will have you tearing your hair out simply due to how poorly optimized it is. It's a great game otherwise, but I can't recommend it to you based on what you said.

If you want a Lucas Arts game, go for Grim Fandango. It's easily the masterpiece of Lucas' adventure games, with a storyline that's both funny and serious at the same time. You'll laugh, but you'll also find yourself invested on what's going on and the overall difficulty isn't too high.

If you go for Legend of Kyrandia, skip the first game. Though a great series, the first game is too much of a guide-dang-it where you're given a ridiculous amount of items that are useless except for one or two you're expected to hold onto for long periods of time with no clue whatsoever. The second and third games remedy this, and I recall loving both of those.

If you want a story and setting above everything, go for Syberia. Out of all the adventure games I have played this one is the game that has dragged me in the most, simply because the setting is beautiful. It's not a comedy, so you'll be genuinely invested in the narrative as opposed to wondering what crazy hijinks the protagonist will be up to next.

I don't consider Telltale Games to be makers of graphical adventures these days. I feel their games nowadays are interactive movies where your input is severely limited and most "puzzles" are absurdly easy. However, if you feel like you MUST see what's in it, Tales From The Borderlands shouldn't disappoint: It's funny, it's witty, and it has an overall pretty good storyline. Alternately, The Wolf Among Us is also pretty good. Or, if you want real adventure games, the three Sam & Max telltalle seasons are great, particularly the third one. Stay away from Tales of Monkey Island, however, since it's not really a good series and the episodic format really makes the Monkey Island setting suffer.

I found The Longest Journey to be quite good, but it's easily the wordiest adventure game I have ever played: You'll have to read, a lot, and sometimes you might find yourself wishing for conversations to be over so you can get back to pointing and clicking.

Last, but not least, if you want comedy I can't recommend Simon the Sorcerer enough, along with Day of the Tentacle. Also, as mentioned by many, Deponia manages to capture that Monkey Island vibe with a useless, widely hated protagonist who's not so much of a lovable jerk as he's simply an idiot. It works well, however.

As for more classic games, I'll agree that the Sierra games are mostly outdated and finishing them without a guide can be difficult, and that's without mentioning the outdated graphics. However, games like King's Quest have been remade by independent studios, completely overhauling the graphics and adding a new difficulty setting where you can't lose the game (ie, all puzzles that could end up in an unwinnable state have been fixed). You can get those remakes in the AGD Interactive Website.

Last, I'll take a minute and add one game I haven't seen around in the thread: The Cave is a cool, witty graphical adventure with simplistic design from the creator of Maniac Mansion. It is well worth playing it, even when it doesn't quite play like other adventures.

Monkey Island, Monkey Island Monkey Island!
But seriously, Play Monkey Island, it's hella good!

This! I loved the Blackwell series and I'm currently playing Texhnobabylon. What I love about games from Wadjet Eye is that they have logical puzzles (no incomprehensible and weird stuff) and have good stories (you solve puzzles for the story and not to get to the next puzzle). And don't let the graphics put you off! They're surprisingly beautiful and fitting when you're playing the games.

I didn't mean that all people should like the same things. That would be so boring. I am sure you recommended those games because you liked them and that is fine. I just wanted to give my point of view about those games, because I thought that maybe someone new to adventure games should begin with something less frustrating.

Just to explain what I meant by illogical or far fetched puzzles. One puzzle that comes to mind is the one with the fortune cookie. First you have to obtain it and that puzzle is perfectly fine, but then you can't open a couple of cookies to get your platypus club invitation, but you have to go to that guy at the docks and give it to him. Maybe there is some kind of logic behind it other than that he said at some point that he's a lucky guy, but if that is not far fetched, I don't know.

I deemed making someone a fan quite the tall order, but you solved that conundrum beautifully. :D

I know they did. It disgusts me, honestly. We will see how it actually comes out and if I can actually play the original like it was originally or if they'll have bastardized it still.

I also have to say. I really really strongly disliked Syberia 1+2 (which I forced myself to complete both of because I wanted to like them, but just couldn't.) Super boring story, really really lame and flat characters (all 2 of them), no "puzzling" at all, just click click click click things and move on with the "story." I seriously wish I could unhear the stupid robot saying "Kate Walker" (ohhh "Walker" SOOO clever, NOT!) I can't NOT recommend these games strongly enough. But who knows, you might like them.

I also found Broken Sword 1 to be extremely boring and poorly done, so much so I tried to play it twice and was so un-enthralled and bored (I call it Boring Sword) I deleted it and the 3 others from the series I bought and moved them to the "likely will never play" list. But hey, lots of people love them, you might too.

I also found their play-styles to be too easy non-challenging (there was nothing to "figure out", it was just all obvious things with lots of clicking action to make it feel like you were doing something, but it could have just played itself for you while you watch.)

Just sharing thoughts because they add perspectives for you to try and figure out what to play!