I have discovered that a lot of the problems I have with many fantasy stories and games seems to stem from settings with very concrete backgrounds; All histories and science but no room for anything really mythic.
What do I actually mean by mythic? Stories, each one ages old, that explains something about the way things are in terms of heros and villians. These stories stand largely on their own, even if they are part of a greater mythic picture. And importantly myths conflict with each other. The best myths seem metaphorical, even when they contain some concrete truth.
This struck me while reading Open Grave, the D&D 4e undead book. D&D in particular has a very strong tradition of settings where the early history of the world is very well established. Given the sparseness of the D&D Points of Light implicit setting, the concreteness is unfortunate. Open Grave presents a very scientific explanation of undeath in the setting. The result is some very cool ideas, but none of the horror that I want to associate with undead.
In contrast, the Wheel of Time series of novels has done well at presenting both the explained histories that the people of the world knows, alongside the rumors and speculation of ordinary people of the world. Another example is Trail of Cthulhu's chapters on the various Gods and Great Old Ones of the setting where multiple possibilities are presented for the keeper to consider.
Hellboy is another good example. The characters could realistically know about the myth and murky past of the world but it is generally shown rather than explained and is presented in a much more snapshot view. There are lots of snippets for the reader to see, but the bigger picture eludes them.