I think it pays to have multiple decks. In general, to wander around the world, you can do it with a lot of different deck types, but you can also scale it to the type of area you are going through. Kind of like pre-sideboarding. If you are in black territory, run around with your White/Red White Knight burn deck.
As far as tackling the dungeons, the biggest challenge is the fact that you don't get a second chance. Find out as much as you can. The two big questions are 1) Does it start with something in play, and 2) Does life "loss" carry over.
If it starts with something in play, sometimes you can use this to your advantage. For example, a deck that starts with Living Lands or Kormus Bell in play plays dead to a W/R deck running Lightning Bolts and Swords to Plowshares. Since your opponent's lands all enter play with summoning sickness, you can often win before you even start.
If life "loss" carries over, you can use this to your advantage as well. See, you go in with your starting life, but each battle keeps the previous life total. Pull out your deck loaded with Spirit Link, Ivory Statues (is that what it's called? It's been too long...gain life equal number of card in hand in excess of 4 each upkeep) and don't be afraid to Swords to Plowshares your own unnecessary creature before attacking for the kill.