Your options are sort of limited here. You're asking: "In an age where people have not built any large above-ground structures, what sort of large above-ground structures are there?"

You need to either reach out to fantasy or think outside the box.

### Natural, mazelike terrain
* Open-air passageways through an icy tundra.
* Mountains with winding goat-paths, and a spattering of caves.
* A spirit-touched ravine with winding paths between its walls.

### Dwellings created by others who _can_ build big things
* An ancient, crumbled city - ancient man, perhaps. Dilapidated castles, caved-in houses, no dungeons and a lot of missing rooves giving you open air.
* A faerie dwelling. Celtic mythology was full of spirits, and if your setting's anything like theirs, yours might have its fair share of them too!
* A city at the top of giant trees. Pathways connect the trees, as many or few as you want. Instead of large stone walls separating you from another point, there's just a large gap and a long fall - unless you have the resources to cross the gap, or climb down and back up again.
* The Lost City of Atlantis.

###Send them elsewhere entirely
This is definitely cheating, but can let you have some fantastic structures that can't exist in the real world. Whatever those would be. Like the [Maze of Tzeentch](http://wh40k.lexicanum.com/wiki/Tzeentch#The_Maze_of_Tzeentch).

* There's a place where another plane meets this world and the players have to venture in.
* The heroes experience a spiritual journey in their sleep - ooOoOOoooOOOOooo!!