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, or cracks in its ice. Effectively a cave minus the ceiling.
* Mountains with winding goat-paths, and a spattering of caves.
* A spirit-touched ravine with winding paths between its walls.

### Natural obstacles to make crossing land hard
* A land teeming with rivers.
* Great islands separated by vast water. Some may be connected by natural bridges (sandbars, stone arches connecting two cliffs), others by artificial bridges (sturdy bridges, vine/rope bridges, ziplines). Alternately they may be connected by underground passageways or nothing at all, with reliance on boats or other transport to cross - if anyone even lives there to offer such services.
* Somewhere with lava flow - current with glowing rivers, or recent with hot stones. Mind you, [Lava comes in a lot of forms](https://en.wikipedia.org/wiki/Lava) and could be tricksy - that page alone has a couple of photos of lava sealed beneath rock, so that it might just look like rock (or mysteriously flowing rock if it's not still) - until you step in it.
* Heavily overgrown forestry.

This section isn't comprehensive - other answers have provided locations that could fit here and I'm not sure I should pilfer them for the sake of making this list comprehensive.

### Dwellings created by others who _can_ build big things
* A raft city built on a lake. In the ancient Celtic age, this may have been quite a technological feat and wonder, and might be a natural expansion upon [Crannogs](https://en.wikipedia.org/wiki/Crann%C3%B3g). The Wiki article will fill you in on how common they were, but they're a fairly ancient concepts (though common only in Scotland and Ireland). Come to think of it, I wonder how it's anchored - it would be a _shame_ if anything were to happen to those anchors...
* 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!!