I've got a couple of dwarf PCs being sent out from the kingdom to reinforce a new stronghold on the other side of a portal that functions once in ten days. They'll be headed to the bottom of a large vault where a team of dwarves is building an outpost, having discovered a good vein of iron there.
However, the surrounding area is pretty much unexplored. They'll have a fortified place to rest, where a 9th level dwarf cleric can provide relief from deleterious status conditions, and where they can purchase necessary items once every 10 days via an enterprising merchant using the remote portal.
PCs are 4th level. What would you put in the surrounding area?
So to start, you only have an XP budget of about 350, per Encounter; so, obviously you're either going to have to make for some highly interesting encounters, or you're going to have to put them up against more than a few insurmountable odds.
But here are some things that I can suggest.
Organized Encounters
Wights. Wights [MM, 262] seem as though they could fit. Perhaps prowlers in the Underdark, the smell of the living dwarves has drawn them t the dwarves and they are trying their best to pick them off one by one. Otherwise, they could be angered that the dwarves have disturbed the area, which they have always believed to be a sacred place, or some such.
Drow. Obviously a classic staple of the underdark ("Classic" is a loose term, I suppose). Can't go wrong with Drow. [MM, 94]
Cults. Worshipers of any cult that might congregate in the dark places of the world, or send worshipers to collect something from the dark places of the world would do well here.
Goblins. After Giants, I don't think there's anything that goes quite so well with a Dwarf as a Goblin. Natural enemies, you can't go wrong with Goblins either.
Giants. You could always consider dumbing a Giant down, or creating a weaker Giant. Call it a baby version, or just some under-nourished, under-trained, ostracized giant that was rejected from some society or another and has been wandering the Underdark.
Troglodytes. With some tweaking (or not) you may be able to work Troglodytes in, in small doses. Maybe they could have some affiliation with Drakes, or other reptiles (see below). Though, I must say, I was surprised to see how much higher their default level seems to be geared for, in comparison to the last two editions.
Ranndom Encounters
Drakes. Drakes can be good for your underdark scenario. Excluding the Spiretop drakes, drakes can more or less fit into the underdark (with a little tweaking). Something such as a few Needlefang Drake Swarms (MM, 90) could do some damage to your PCs as a random encounter. The PCs stumble into a kind of "cave" that turns out to be a Drake's Roost; have to encounter a Needlefang Drake swarm and/or another Drake of your own design, most likely a Solo or Elite Guard Drake with some tweaks for flavour (some abilities added to reflect an angry Mommy/Daddy drake guarding his/her nest).
Crocodile. I know how it sounds, but let me explain. We've all heard the old myth about a Crocodile being flushed down the toilet as a baby and then growing up in the sewers of a large city. The same could apply here. If the place the PCs are near is anywhere close to a large city, you could say that the Crocodile ended up in the drainage system and managed to crawl down into the Underdark and, somehow, survive for many, many years. This would make for one angry Crocodile, and one possibly interesting encounter (The Visejaw Crocodile [MM, 45] also happens to be a 4th Level Soldier, so maybe if you wanted to add two together or make some changes to the Visejaw, you should be good to go)
Bats. Good ol' bats. They fit into just about any subterranean adventure, as either a Swarm or an individual creature (but with a particular emphasis on Swarm). They'd go great as a supporting Random encounter for any other encounter you're able to think up. Imagine fighting against insurmountable odds, only to be able to stir up the bats and make a break for it; or, their foes, fighting against insurmountable odds themselves, doing the exact same thing to the PCs; or, of course, having the bats enter during a Skill Challenge situation (i.e. trying to cross a bridge that is slowly falling apart, climbing a difficult cliff, etc.). Bats can always make things interesting, when used to support encounters. And there's always the Fire Bats [MM, 27] too.
Bulette. Obviously, unless the Bulette [MM, 38] was re-designed at a lower level, the PCs wouldn't survive this fight (especially with only two of them). But having a Bulette come into an already ongoing fight, its slumber disturbed by the sounds of battle, can lend to some kind of cinematic flair; or the PCs can stumble across one accidentally, and have to do their best to safely by-pass the Bulette (e.g. through a Skill Challenge), or threaten invoking its wrath.
Undead/Skeletons. Undead [MM, 274 "Zombies"] and Skeletons [MM, 234] pretty much fit into any niche. Just create an abandoned fortress, an ancient battle site, a mausoleum, or some other site where there may be a lot of dead bodies. Also provides opportunites for looting.
Stirge. Stirge [MM, 248], much like bats, can be effective as support for an encounter, possibly working with Undead or other non-living creatures (lest they try and suck the will to live from them too).
Spiders. Big Spiders, small Spiders. Any kind of Spider will do.
Environmental Dangers
Cave-Ins. Natural Cave-Ins are always a threat when underground. Perhaps you can have the PCs aid the dwarves when they accidentally hit a rock formation that collapses on them. Otherwise, add a Cave-In to an encounter to make it a little more deadly. (Can be artificial or natural)
Stampedes. Some large animals of the Underdark (I'm thinking some kind of Homebrewed Elephant-like, Rhino-like creature) stampeding through the Underdark in a big horde. The PCs have to run, jump, crawl, climb, and much more to escape being squished.
Dangerous Plants or Other Organic Matter. Plants that cause diseases, explode, or in some way attract larger dangers to the PCs can be a danger. Likewise, something that has healing properties can work to attract the PCs, perhaps as a kind of mission that one of the ailing dwarves constructing the fort sends the PCs on.
That's about all I can think of. But that should be enough to at least get you started thinking about ideas.
Best of luck.
It's 3.5 btw. I have all the applicable books for it, fear not.
Best to use in a Minnie quest for finding water.