Puzzle Box is actually pretty easy if you just know what door to take. I think people had difficulty with Arkngthand because it was usually their first big dungeon in the game. Lots of rooms, a couple of early inaccessible areas, lots of enemies, etc. Usually you find it via process of elimination, but some folks just never checked the second floor.
Arkngthand was hard because the map layout told the player to go the wrong way and then go much deeper.