Kanto: Probably Diglett's Cave, since that's pretty much the only optional dungeon in the game that doesn't house a legendary bird.
Johto: Mt. Mortar
Hoenn: Scorched Slab
Sinnoh: Sendoff Spring, Wayward Cave
Unova: Most towns prior to Castelia in both BW and BW2, Humliau City, Letimas Town, some of the caves in BW2. Holy shit, I just realized BW2 had a fuckload of stupid interconnecting caves.
Kalos: Never played, so I dunno
