While I've stated I do prefer the linear dungeon design, another thought I had while thinking on this topic, what about them just doing a partially randomized dungeon? Say the bosses of the place or the layout is different each time while maintaining parity in the overall difficulty/time of completion?