Adom and Dungeon Crawl are my favorites. I like Adom's world / overall game structure, and the corruption system serves to constantly push the game forward instead of encouraging sitting around and scumming for stuff (grr Angband). Both of these are also pretty fair games, there's few instances where you die and not feel like it wasn't because of a mistake on your end. They're also fairly straightforward to figure out entirely on your own.
Dwarf Fortress's adventure mode is fun roguelike-type game too, though its not really a complete game on its own yet.
I used to like Nethack a fair amount, but, once you learn its tricks, its almost impossible to lose at it (barring random wands of death and the such at the beginning of the game).
I'll often be playing some roguelike on my computer (or other turn-based game) while waiting between matches in SC. Helps pass the boredom of waiting for a new opponent and lets one be a lot pickier about what connection speeds one will accept without getting bored. (SC5 is mildly annoying in that it doesn't have as loud/distinguishable of a sound when someone joins your lobby as SC4 did)