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.
- 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!!