If I were to redesign Terraria's dungeon, I would follow Starbound's example. Starbound uses dozens of separate 'room' examples that while similar, are far better designed, more pretty, and present more of a challenge than Terraria's random, quite frankly ugly generation. The rooms have multiple entrances and exit connections that are placed together by the generator based on opening size and assembled like legos into a coherent whole. If the developers made a hundred or more premade dungeon rooms (I'd love to just spend a few hours building example rooms right now, actually. I'll probably do that then take pictures.) and used this method to assemble the dungeon, everything would look far prettier than it does now and provide more dangerous traps with better layouts.
You would need a lot of dungeon rooms for enough variety though, and this is an area where Starbound is struggling, but improving in.