DS AK of Lugonu. I've done Mahkleb, it's relatively easy with an accessible "kill" button, and lots of good summoned friendlies.
Lugonu just seems like a cold bitch by comparison. "Here's a power to return to the worst place in existence." "Here's a power to hurt yourself and blink." "Here's a power to solve your problems but rob you of half the reward, and might possible get you killed if you're not paying attention while moving."
Banishment is like the one saving grace of the religion...but even that has a caveat. You don't get no free rides with Lugonu. Reading over the other stuff, there are a couple other perks...but man. Mahkleb supports his followers to help them get the job done. Lugonu is like "meh, get out there and do stuff, the abyss is here if you want it."
The blink frogs, it's just shocking how much damage they do. Frogs in general are behemoths, but damn, a pack of them and I'm down 100 HPs.
I guess what kills me is I'm 10 into armor already, and my platemail, while giving great AC and damage prevention, still robs me of half my attacks at that level.
A better weapon, a tier up from the junk on the first 10 floors, has eased things up a bit. Ultimately though, the lack of mass explosions of instant damage, friends or other effects to throw the monsters off, pretty much leaves straight melees fucked, for the size and numbers of stuff that SS throws at them, on top of the (very awesome) mechanics.
I'm pretty sure the only thing that's stopped me from tearing my hair out in total frustration on this run is a good dose of magic resistance that came my way early on.
It's always like this though. That spot between levels 6 and 15, and all the stuff in between, is a total pain in the ass as a mostly melee character. Past there you can start to hybridize, get a ring of the gourmand, all that tertiary support stuff that supplements having an awesome race, innate powers and spell access.
Even though I've said it before, I feel like melee-focused characters need something extra to get them through combat. Like a sweeping attack that hits all adjacent squares at once, kill shots, something.