Could I recommend
TOME4 and
ADOM? These are the two major roguelikes with robust questing systems. I've only played Crawl and Nethack, so I can't personally endorse either of these, but you still might want to try them. Both of them have graphical support, but note that ADOM's was added very recently, so there might be some problems. Also note that Crawl's no-spoiler and no-scumming philosphy is unusual among roguelikes. You'll probably have to read spoilers to win at these games. For example, in ADOM:
Cats are a very common enemy. Near the end of the game, you run into the "cat lord," an invisible high level monster which will attack you if you have killed any cats. By this time the player will have run into hundreds of hostile cats trying to kill them. There is no indication anywhere this has any effect. If you kept this conduct, the cat lord will instead give you an artifact.
On the note of quests - I think that quests work well in standard games but are hard to get working well in roguelikes. You need a lot of control to design good quests, and that doesn't mesh well with heavy randomization. Part of the reason there are so many spoilers in the games I mentioned is the quest system. I think the Mystery Dungeon manages to do quests reasonably well, but their quests are very simple - kill this one bloke, bring somebody somewhere, retrieve this one item, find this missing person etc. Note that most of your examples involve uniques, which are already the most spoiler-based part of Crawl.
On IRC my nick is reaverb. I play online under the name reaver, though.