There are a lot of different types of difficulty, and I think that in a discussion like this it's important to distinguish between them.
I consider a game more difficult as the more perfect my play needs to be in order to win. Another way to put it would be to say that a game is more difficult as the number and size of mistakes I can make before losing decreases, the game can be seen as more difficult.
I consider a game cheap if I can lose due to factors completely out of my control. Since roguelikes are as random as they are a "perfect storm," as Tycho put it, will inevitably come up from time to time.
My preference on randomness is that the game never presents the player with an unwinnable situation, but it should present them with interesting and difficult situations, requiring them to constantly adapt and change their plans to survive.
Then there's the subject of spoilers. In Nethack in particular, there are a lot of ways you can die off that you would have no way of knowing about, but once you know about them, you can avoid that death in the future. Is this a challenge or is it just being cheap? I'm torn because I don't like dying to a circumstantial thing that I could never have known about, but on the other hand I do like experimentation and discovery.
I would say that Mage Guild is a good example of a game that has difficulty, but is fair, and IVAN is a good example of a game that is both difficult and unfair.
I have to disagree with AmnEn's assessment on difficulty curves. In a more traditional game where a player can save and pick up from the same spot when they die, gradually increasing difficulty is generally viewed as good design.
Roguelikes aren't that way though. They're designed to be replayed a lot. Especially the beginning. It seems tedious if the start is too easy for you, but the middle game is at about your skill level, so every time you want to take another shot at that mid-game boss you have to slog through an hour of content that you know is too easy for you.
One way of handling it that I like is by rewarding the player not just for completing a section of the game, but for how well they completed that section of the game.
I'll choose Angband as my counterexample. In Angband you can replay any dungeon level as many times as you want, getting money, equipment, potions, and experience until you're satisfied and move on. Anything that doesn't kill your character you can fix with time, and the only things that really matter are that your character is alive, and that they and their equipment are up to date.
I'm going to use Mage Guild again as a contrast. In Mage Guild you cannot replay old content, and so it's important to balance the preservation of your early game resources with your character's survival. Do well and you'll be stocked with a good supply of potions and abilities for the late game, but if you come across difficulties, you may have to learn a weaker spell for the short term or use a valuable potion early that will make things more challenging later on. That way the beginning can still be fairly easy to survive, but almost as important as survival is surviving while expending as few of your resources as possible.
