I would prefer that not so much attention would be put into huge dungeons or hard to navigate labyrinths but into huge mysterious areas with secret sections and random puzzles. It would be very interesting to have special or random encounters with NPCs (see Fallout and Diablo I) being generated inside dungeons.
Procedural Dungeons don't have to be predictable. It would be expected that some parts of a dungeon would crumble to reveal a cave area or and underwater river. Some dungeons might be occupied and modified by rogue wizards and mages and show distinct signs of what happened inside in the last years.