A proper (game) dungeon, in my opinion, has three qualities:
It must have a complex and challenging layout. I refer to this as "environmental challenge." Multiple floors/levels interconnected at various points, portions of some floors accessible only from certain sections of another floor (and optionally, individual levels/floors sharing various elevations as opposed to being completely flat), dead ends, branching forks and intersections, switchbacks, one-way exits, single exits that can lead to multiple destinations, pitfalls and trap doors, portcullises or portholes allowing vision but not immediate passage, secret doors, ladders, teleporters, et cetera.
It must also have rewarding and challenging interaction. I refer to this as "not being designed for retards because they 'just want to relax after work'." Cryptic messages and clues, various kinds of environmental or self-contained puzzles, needful key items to uncover, levers to pull, hidden buttons to push, pressure plates, traps to avoid (and maybe disarm), hard-to-spot reward items or equipment, and observational mysteries (i.e., observe some creature or character's behavior to figure something out; just for example, following a mouse back to a crack in the wall).
Finally, interesting monsters or creatures with varied traits, behaviors, dialogue if applicable, and needful loot implemented in the dungeon via thoughtful encounter design can't hurt.