Well, AgingMinotaur touched on a lot of topics I find interesting, so this is a long post.
On the other hand, I keep coming back to ADOM and immensely enjoy the feeling of an actual world/story going on, even if the prose and plot would be just laughable in any other medium (Khelevaster's monologue epitomizes this).
I really like ADOM’s plot. For instance, I feel like the whole idea of "corruption" in ADOM is brilliant. Corruption/chaos/entropy is such an interesting and multifaceted entity in that game. It is framed as having some characteristics of an infectious agent or contaminating substance, some characteristics of ionizing radiation, and some characteristics some sort of cosmic force that wants to enslave the world (sort of like the way “sin” is sometimes referred to by Paul in The Book of Romans).
Obviously, the process of becoming corrupted also involves the idea of giving up your humanity in exchange for great power. You can do what amounts to making a pact with the devil to temporarily become very strong through corruptions, but you know they will be the PC’s downfall, because ultimately the only outcome of embracing corruption is to become a writhing mass of primordial chaos.
I think a similar idea was implemented in another game over a decade ago (the name of which I forgot), except in that one both order and chaos were deadly if taken to extremes. Acchieving a state of “pure, crystalline order” as they put it, would ultimately kill the PC. I guess that makes sense, because in a zero entropy state, wouldn’t a person have to be in some sort of crystalline form?
I’d really like to see a game that was built around balancing order and chaos, instead of just avoiding chaos. And I’d also like to see a distinction made between good and evil and order and chaos. A person (or diety) can be very disorganized, or even crazy, and still be kind and just. On the other hand, someone can become obsessed with rigidly following a set or rules or belief system to the point that they become a dangerous zealot who values those rules more than actual morality.
Incidentally, you really should try Caves of Qud. Heavily inspired by ADOM, except the setting is actually quite original, and the prose isn't half bad. For kicks, hack down the zealot in starting village Joppa and read his book of religious doctrines (sells at a decent price, too). TOME also does lore in the form of paper scraps lying about and such, although I never got the same kick out of that as I did from ADOM and CoQ.
I will check it out. Your last post does illustrate a very important point related to in game lore. It sounds like what makes the zealot's book so interesting is that, far from being a mandatory plot element, or even an unobtrusive optional element, it is actually hidden.
In this situation, learning more about the plot is an act of discovery, of uncovering secrets about the world. You wouldn’t just give these sorts of tidbits to the player any more than you would give them a powerful artifact at no cost or risk to them.
I think it would be interesting to have a game where these secrets contradicted the conventional way the game world was perceived by most NPCs and reported to the player. What seemed like the “normal ending” might be revealed to be an absolutely terrible outcome, once the player did a substantial amount of this plot related digging in subsequent play-throughs.
This would be sort of an “everything you think you know is wrong” approach. Essentially, when the player made what appeared to be the right choices, they would naively be helping evil forces that seemed superficially good.
Re: reading real world mythology, akeley mentioned it's not really comparable to novels, for instance. While that's a valid point, there were a bunch of works that were written precisely as art, and I'd be hard pressed to mention a literary work that outclasses Ovid's Metamorphoses, for instance. I suspect you'd find Ovid or Homer a bit stale (although they class among my personal favorites, like evvah biatches). Still, you might give Gilgamesh a try – short, sweet, and very ancient – or, for a different beast, and if you enjoy a faerie tale style, The Thousand and One Nights, although that's not mythology per se. Campbell et al., that's all pretty theoretical, right? There are also a ton of books that simply retell the myths. Many are aimed at kids and young adults, but can be quite entertaining, nonetheless.
I’ve read a decent amount about the Gilgamesh epic in the books that I mentioned. I don’t know, I just couldn’t get into it very much. I can’t help but think that the reason those types of myths are considered great is because so many later stories were inspired by them and built on them, rather than them being great stories themselves.
I think a RL story/setting should ideally have randomized parts. Doing that right has proved damned difficult, even though it *should* not be too hard, in theory 
When it comes to a randomized story system, what about just randomizing the certain "intentions" of certain prominent NPC's? NPC's would always have the same alignment, like chaotic or lawful, but whether they were good and honest or evil and dishonest would be the random part (remember, I want to separate how chaotic a character is from how moral they are). The probability might be weighted so that a character was usually “who they were supposed to be” but without it being a certainty.
Since you could never assume an NPC was honest, speech skills that could detect dishonesty would be important. Also, if the PC was desperate, they might rationally decide to take a chance and trust a normally dishonest character. This would make sense, because it is possible that character had been marked and honest that play-through.
The idea of lying to the player in various ways is an interesting one to me in general, actually.
