The following scenarios are all written to require no previous adventuring, no NPCs telling the party about a dungeon, no need for a mcguffin and no promises whatsoever about what the dungeon may contain. I've never used any of these - they are freshly invented since yesterday.
The party has settled in for the night at an inn located in a large city. Not long after midnight, the thief hears footsteps on the roof. They cross the roof towards the lane outside the inn and there are two thumps as people drop to the ground. The thief is reminded that there is a window that looks over the street in that direction, and naturally the thief rises and looks outside.
The thief sees two figures arguing silently next to an open sewer grate. One is holding a cloth made into a sack, and this seems to be the point of contention. The sack gets shaken up quite a bit. Finally, one gives up the sack and climbs into the grate first. The second figure lowers the sack and then follows, pulling the grate back in place.
The thief naturally goes out to search the street and finds a single earring worth about 10 g.p.
If this does not encourage the thief to follow, with or without the party's help, then say that the next day the thief is in front of the inn, eyeing the grate, remembering the night before. A young boy, well dressed, appears and sits next to the grate, eating an apple. The boy opens his satchel and draws out a small roll of parchment. When the boy thinks no one is looking, he extends the parchment towards the grate. The thief sees two fingers rise above the level of the grate and take the parchment. The boy finishes his apple and goes away.
The dungeon starts under the grate. The first level is a second-rate thieves guild, but there may be lower levels dating back centuries containing who knows what.
The party finds themselves in a small village of about 35 buildings, where they hope to pick up enough food supplies to begin (or continue) their journey. The local grocer has nothing in stock, but he promises that he has a storehouse two miles distant - could the party wait for an hour while he sends his helpers out to get it. He offers to buy the party a drink at the local alehouse for their trouble.
The alehouse seems to be under repairs - and the party is asked if they don't mind drinking on the back veranda, since it is a nice day. The veranda overlooks a rather marvellous, attractive valley with small dairy farms scattered along the bottom. About half a mile away, on the opposite side of the valley, the party can't help but notice a large burnt out area surrounding an immense, blackened manor. Upon inquiring, the tavern keeper admits that the house was the former residence of the local lord, who apparently died in an altercation - about a month ago - between himself, his wife and his wife's lover. It's generally agreed that all three died in the fire. Just now, there's no word on who will be heir to the land, but all is fine as the neighborhood is populated by decent folk.
"Oh yes, the house was searched. It is a great mess inside, all collapsed. About ten bodies were found, the others certainly being servants. No telling what's under the rubble - but no doubt the king will have men here before we need worry about treasure hunters. More ale?"
Under the house, obviously, is a dungeon.
The party has stopped at a roadside inn, a somewhat fortified, ancient place where the rooms are a bit expensive. The owner is a pleasant fellow, generous and anxious to emphasize the age of the inn as this seems to be the chief selling point. The inn was a fort during the time of the ancient kingdom that preceeded the present era.
Mid evening, during the player's meal, the innkeeper approaches the strongest member of the party to ask if he can get some help moving something in the cellar. "My helper's back has been strained," says the innkeeper. "Do you mind?"
Likely, all the party together will try to help, but the innkeeper will assure them that there isn't enough room for them all and that it's perfectly safe. Hopefully, the party can be convinced that this isn't a trap.
The object is an immense iron stove, which the innkeeper needs moved across the small 10x10 foot room under the room's trap door, so it can be hoisted up into the kitchen. "I moved it here when Warner was my helper," says the Innkeeper. "Warner could lift anything."
The character finds the stove incomprehensibly heavy, but with the innkeeper helping, they proceed to shift it across the room. Then, just before getting it place, the innkeeper slips and the stove topples, hits the wall and the rights itself again. The innkeeper is on his butt, attending to his knee, which has been knocked terribly hard. He asks the character to take the lantern from its hook on the wall so they can look at the knee more clearly.
As the character rises and moves towards the stairs into the cellar, he or she detects something odd about the air. It has changed. There's a draft coming down the stairs now, though a very slight one.
Between dealing with the innkeeper's knee and perhaps calling another member of the party, an examination where the stove hit the wall will reveal a quarter-inch slit between blocks, which will be sucking air from inside the cellar (evident from any flame placed close to the slit.
Behind the wall is a dungeon.
While the party is setting up camp, one of their horses is spooked by a huge spider. The spider is easily killed, but the horse has broken free and wandered off. Setting up the camp before dark means that only one player has time to go get the horse.
The horse leads the character on a merry chase. Just as the character nearly get the horse, however, the character is attacked by three kobalds or two goblins (a minimal group of some intelligent humanoid). Presuming the character easily dispatches these, it occurs to the character that these seemed to appear as if from nowhere.
If the character searches, the horse will poke about the immediate area, keeping within a dozen yards of the character. The horse will then step into a hole, make save or not; failure will indicate the horse has fallen down a set of hidden stairs.
Feel free to offer a reasonable chance that the player will find the stairs before the horse, if the character is a thief, assassin, monk, druid or ranger.
The stairs lead into the back regions of a humanoid lair - and a dungeon below that.
While travelling in a forest or in the mountains, a male character moves behind some bushes along the road to pee. As he does, he begins to notice that the soil where he's peeing is draining off a rock, and that the rock itself seems to have an image being made dark by the urine. The player is free to spray his pee a little wider and reveal that there seems to be a carved stone just under the surface of the ground.
Further examination will reveal a buried stone slab, seven feet by four, three inches thick, covered with images and runes.
Under the slab is a dungeon.
Do you see the pattern? Happenstance. So much is easily provided by happenstance.