Syberia is extremely stylish and has some interesting themes, but is rendered unplayable (in my opinion) by "walk as far as possible" puzzle design (the key you need is always the farthest possible point from the door it unlocks) and very slow walking speed. Machinarium is basically a comedy game. It's very charming, but I would actually say its farther from Gemini Rue and Primordia than the Monkey Island games are.
Here's the list I'd give you:
Grim Fandango: peak of style, fantastic writing, okay puzzles and interface, fairly serious though with some humor
Full Throttle: cartoony, but not comedy, with the best depiction of a non-nerd protagonist in an adventure game
Loom: short, easy, but super atmospheric and beautiful
Sanitarium: mediocre puzzles, frustratingly slow walking speed in all but one section, but -- at least when I played it in the late 90s -- creepy graphics and a moody storyline
Broken Sword: Shadow of the Templars: Now seems horribly cliche post-Da Vinci Code,* but had some clever stuff in it; great art, good puzzle design
The Longest Journey: I'm not that wild about this one (lousy puzzles, melodramatic plot) but lots of people do love it, and I enjoyed it passably when it came out; it has some "deep lore" too, if that's what you liked about Primordia
Indiana Jones and the Fate of Atlantis: Not usually wild about licensed IP, but this one captures the spirit of the movies well and offers multiple puzzle solutions
All of these games have no death and no walking-dead scenarios (i.e., where a mistake earlier in the game blocks progress later on, but doesn't kill you). For someone new to adventure games, I'm reluctant to recommend the other kind of games, where you can die or get stuck. Still, in that category, you might want to look at:
Quest for Glory: good puzzles, multiple solutions, great RPG-lite elements, some humor but generally pretty funny
Gabriel Knight: some stupid puzzles (famously stupid as the series went on), but a really cool and fun depiction of New Orelans
Dragonsphere: fairly obscure and fairly derivative, but has some really cool stuff in it
I'm sure I'm forgetting lots. By the way, not playing the Monkey Island series is insane (Monkey Island 2 is probably the best adventure game out there), so when you start moving onto humorous stuff, there are some good options out there, too.
[* And, yes, I realize that Broken Sword was predated by Foucault's Pendulum, which mines the same territory.]
