Many roguelikes have static levels that have something I call the story. In fact even random levels have their own "story", but it's less obvious. Static levels or places have an important role to bring something special to the basic random dungeon generation style, but they themselves can become rather boring, because they are always the same.
Some games try to solve this by randomly selecting different elements for the static level. Sokoban in Nethack has couple of variations for each level of the sokoban branch and I think the artifact can also be either bag of holding or amulet of reflection.
In Sokoban's case the next level would be changing parts of levels to create even more variations of the sokoban puzzle, but I don't know if it's even possible. The hard core solution would be a random sokoban puzzle generator that would create the level and solution using no static parts whatsoever. It could be possible to write such a routine, but I'm guessing it's quite difficult to do.
The story is an essential part of a level theme and more detailed story is more interesting one in theory. Sometimes the story can be as simple as some special type of monster(s) that live in some location. There may be also some treasure you can find either by killing the monster or the treasure is hidden and guarded by the monster. Without a story the level is just a bunch of rooms and corridors you have to explore. Well, nothing wrong with that either, it's just not that exciting.
Trying to find the way to the next level of storytelling is difficult, because you want to avoid static elements but at the same time try to create them using some kind of random or semi-random technique. Quests, artifacts and special monsters are ok I guess, but there could be other type of stories as well, it's just a matter of trying to think hard what could happen in a dungeon other than that.