Like Vault 22. The enemies in there weren't hard to fight, but I've been lost for hours and hours in there because the minimap and objective marker are so unsuited for multilevel 'dungeons', and because there are parts of certain levels that you can only get to from other levels. It's not really something you can adjust with difficulty levels.
Well that's really all about bad map design, both the actual map you look at and the cell itself.
Nothing about difficulty there really. Just bad pathing.
I don't think dungeons should be altered along with the difficulty sliders either, that'd just make them even more tedious to navigate through.
I on the other hand think that puzzles should be altered, not that there are many puzzles in New Vegas apart from that simple one at Mojave Chapter but rather in Skyrim.