Starship Titanic.
You'll be hard pressed to run it, I will admit, and it is a "point and click adventure" game, but man if you can follow it its worth it (hint: there's a puzzle that has the solution in the box art, though likely you'll get stuck on getting the chicken, several hours prior to that puzzle).
In the same genre:
The Dig (sadly, another P&C Adv that has a very early stick-spot as well as one late game "if you don't do this one conversation action, you put the game into an unwinnable state"--so if you end up using a walkthrough, no matter how non-nonsensical that choice of action seems, do it).
Both games are each at least as long as the entire Myst series (not counting Uru).
Beneath a Steel Sky. About $5 on GOG.com [Good Old Games]. Runs on modern computers if purchased that way. P&C Adv, great story. I managed to finish it with only minor help from a walkthrough.
Torin's Passage. Unknown if this can be found or run on modern operating systems. P&C Adv. Beat it once due to a "find the spot" puzzle utilizing audio hints (click in this vaguely large area, click in this smaller dime sized area, click in this....I only ever found it once and was unable to replicate the feat later). Game comes with its own hint/walkthrough system (it never directly tells you the solution, but gives you enough information that you should be able to figure out what to do).
AI War. Its on [Steam/Stardock] for about $20. Tutorial mission--though the instructive portion was short--took me 12 "Real Time" hours to complete (I was running in 10x speed for the most part, near the end). Great multiplayer (up to 8 players vs. the two AIs). Insanely difficult AI (no, its not cheating, it plays by an entirely different set of rules).