I suppose one thing I don't like about dungeons is that they don't really provide any mental challenges for the party. It's mostly physical. You travel down a corridor, you deal with monsters, you might come across some treasure, and you might come across some traps. Now the mental challenges I am speaking of aren't making a number of skill checks. I am talking about things like riddles and puzzles the party must solve in order to enter the next part of the dungeon or to open up the treasure vault. Stuff where a skill check isn't going to be handy, and where it's more a matter of being lucky/unlucky.
Here I was thinking dungeons are pretty famous for including riddles and puzzles. Those are the parts I don't like as a player, but they are definitely there.