I was a big fan of NH until 3.6, now it is too difficult so I switched to Evilhack which has been a breath of fresh air.
But you can't be claiming that 3.6 is too difficult if you're comfortable playing EvilHack. EvilHack is clearly more difficult than vanilla. :D
But I get the breath of fresh air. I was always playing Valkyries or Wizards and when I first entered the Tourist quest, I was hooked on getting more different levels and that was one of my main focus when developing UnNetHack.
Like you said, that feeling of seeing a totally unknown level is a real rush. Now I am downloading and trying UnNethack :)