I would second (or third or whatever at this point) "Environmental Encounters."
The Underdark, insofar as I've ever envisioned it, is supposed to be a HARD place. Difficult to get around. Difficult to navigate. Difficult and arduous to just move through. Deadly because of its violent/evil/otherworldly denizens, sure. But instead of somewhere SO populated with life, entire races with cities and trade routes, not to mention its own animals and plants/fungi ecology, it should be a virtual desolate wasteland of a place.
Encounters with creatures, yes, are more interesting/entertaining for most players...but not really creating a mood or sense of this place you're actually in. And no one really wants a skill/ability check-a-thon...but THAT'S the sense [I believe] your players should get!
"This sucks!" Ought to be the prevailing attitude and sentiment of a party of PCs moving through the Underdark.
Combat/living encounters should be few and far between...so rare, in fact, that the player's are getting surprised half the time when they happen. And treasure to be found/collected/won should be next to non-existent...unless one happens to be in one of these (exceedingly rare!) cities/trade centers...comes across a caravan with some booty to claim.
I'm talking about tables that cover stuff like:
1. Dead end. You must spend the next 3-18 (3d6) hours finding a different/another passage that leads in the direction you wish to go.
1a: Dead End with Fissure. Creatures of larger than Small can not fit through. 50% of these fissures will shrink after 20-50 (d4+1) feet to a size only Tiny creatures can fit through. And 50% of fissures of any size do not lead through to anywhere.
2. Flooded/Ground Water corridor/chamber. The passage or chamber you are in slopes slightly downward to come to a water's edge. There is no way to determine from this "bank" the distance this water extends. Do NOT roll for aquatic creatures. 50% of these areas do not offer enough head space for air breathing creatures to pass through and/or swimming underwater will expire before finding an area/pocket with air to breath. Figure out a way across the water (if possible) or spend 5-20 (5d4) hours looking for a way around the flooded area in the direction you wish to travel.
3. Cave In. Simply put, rocks fall. Everyone might die. Devise appropriate AoE and DC for save rolls to avoid damage for those at the area's edges and halve damage for those within the AoE. Figure out a way through, spend 3-12 hours removing the debris or 3-18 hours to find another passage/way around in the direction you want to go.
4. Minor Tremor. Roll d20 to beat DC10. Failure indicates #3, above, occurs.
5. "Impenetrable" Darkness. There are no glowing crystals or luminous lichens here. The magic of the world pervades the lightlessness this area has been in for millennia. Darkvision (mundane or spell or magic item) will not function here. You will require a light source, if you do not have one in effect already. [It is the UnderDARK, after all

]. Creatures with "Superior Darkvision" (as all Underdark natives will/should possess) see at half their normal range. This area of effect can be any distance the DM designates. Cunning or intelligent Underdark creatures may use these "darkness" areas as a barrier for territories or disorienting trap/prey along the edges. The area with a light source is still considered lightly obscured area.
6. "Solid" Darkness. There are no glowing crystals or luminous lichens here. The magic of the world pervades the lightlessness this area has been in for millennia. Neither Darkvision nor Superior Darkvision will function here. Your movement within this "solid" heavy fog-like darkness is halved. Light sources of any kind other than the Daylight spell, only illuminate half their usual area. Underdark denizens that rely on sight as a primary sense avoid these areas whenever possible. Underdark natives (and experienced PCs after some time/comparisons) can tell (based on the distance light goes) before entering an area of darkness is "solid" or "impenetrable."
7. Crevace. There is a break in the ground, d8 X 10 feet across, with no discernible bottom. It crosses the entire length of the passage or cavern you happen to be traveling in. Device a way across or spend 3-18 (3d6) hours trying to find a different passage/way around this passage.
8. Major Tremor. Roll Dex. save to beat DC 10 of be shaken from your feet. You begin your next turn prone unless assisted to your feet. There is a 50% chance a Cave In (#3) and a 25% chance of #9 occurs on the following turn.
9. Lava breaks through the passage/cavern wall and begins to fill/spread through the available area at a movement rate of 30'. This corridor/cavern is impassable after the lava cools and solidifies.
10. It's ALIIIIVE! Roll on the available Wandering Monster tables for creatures appropriate to the terrain the party is in.