Dungeons change their appearance in the world map based on their level of completion. Every different class a dungeon has been defeated with, and every badge, adds one point to the dungeon's completion score.
At 0 points (never defeated), a dungeon has a smaller icon.
At 1 point, the dungeon grows to full size.
At 14 points, the dungeon will display a silver cliff effect around its edge.
At 28 (29 if you have the special edition), the cliff will turn gold.
And at 29 (30 if you have the special edition; this requires you to beat the dungeon with every class and earn every badge), the cliff will be striped in different colors like a rainbow.