I've been playing and running D&D for years, but I don't feel like I've done or run very much actual, you know, dungeon delving. Torch-lit exploration of dark, infested, horrible subterranean locales, packed with treasure that no one has had the wherewithal to bring out into the light. Until, perhaps, now.

Since I never seem to like doing anything simple when I can do it totally backwards, my preference would be not to prearrange the dungeon, but to make it up as the game goes, with input from the players. Or, if they don't feel like offering input, they can live with what I come up with, which I guarantee I'll enjoy.

4th Edition, yes, but not just fight after fight. At least, that wouldn't be my intent. I don't think I'd want to focus on "story" in the sense of some prewritten plot, but my hope would be for an interesting build up to a goal of some kind, something we could look back on and feel like had a story to it. I tend to gag at the word "sandbox," but I do think I'd rather have some things going on in the dungeon (again, inspired by player input, if they want to provide it) that the PCs could involve themselves with, or not, and either change the situation, or let it change itself.

Thoughts?

You'd need a proper dungeon creator. Something with random elements, but an internal logic to it -- not just a few 2d6 tables that mash together boring hallways with empty rooms.

With the right dungeon randomizer, you could even use it on-the-fly. Then no one would know what's around the corner, even you. Turn 4E into a rogue-like.

If you want detailed dungeons with internal logic, I can recommend an old book that does just that. It makes great dungeons, but requires some time invested in the details.