Can't help but to think of the "unfair platformer" flash game here. If you haven't played it, it's a regular platformer game like super mario, except it's littered with completely invisible traps that you need to learn by heart via trial and error if you want to get through.
Though you could add a "Turn off warning indicators" box into the options for those who want a greater challenge. If you feel like obscuring or hiding information is a good way of creating a challenge at least. But then you could also put tape over parts of the screen. Another good option always is to hasten cast times of mobs to force the player to react faster, except this screws over people with higher latency. Other than that, you can simply give the mobs more abilities to consider - the only really feasible way to create interesting difficulty in the current setting IMO. Simply adding HP and damage is fairly boring and more importantly, very prone to become irrelevant once better gear has been acquired.
Making something positively difficult, as in: Engaging but not unfair, isn't easy, especially in an online environment. And then there is that other issue: Rewards. One of the reasons why the calls for higher difficulty are often frowned upon by the so called casual masses is because people do not just want a challenge, they also want bragging rights and exclusive rewards associated with it. Essentially, a medal that says:"I am better than you." And that's where the discussion tends to become messy and devolve into namecalling.
To pick up the class quest idea from earlier in the thread, a good implementation would be to have a difficulty promp whenever such a quest would spawn enemies or commence duty. You get a slider and then you can pick any option from "In your sleep" to "Unfair", with the spawned mobs adjusting accordingly. Rewards are identical, it purely comes down to preference.
Would that sort of thing satisfy people? I would wager the common response would be:"It's a start...".