With a lot of scenarios like this -- where I have a bunch of ideas of end goals that will be boring if found directly -- I like to work backwards. Here's what I mean:
First, make a list of possible destinations: abandoned statue park, collapsed arena, well-preserved forge, still-inhabited hovel. Decide how interesting you think each one will be, think up what can happen there, think about which players will have fun there, how it will tie in to the overall setting and theme and plot, and so on.
If there are things only likely to be of minor interest -- worth ten minutes of the party's time for flavor or to find a minor item -- they go in the "places you can just find" list. These places can be found, looked at, and then left. They're very minor encounters.
More interesting locations get a build-up. The forge is of particular interest to two of your characters -- the dwarf and the artificer -- so you know that you can get lots of mileage out of it. You want to build a trail of breadcrumbs leading there. What can that trail look like? Maybe the forge's final location had just opened. The previous one still has an etched-metal sign in front that says "Smithy now at the south branching of the Elbe." How do they find that sign? Maybe it was well-known and a signpost somewhere else still points to it. Maybe the old address is in a ledger book found in another location.
Make the trail as long as you think will be interesting. As you develop more and more incidental locations, you can make them intersect and branch. The hovel's door is an large ancient shield, and its rear has a trademark on it. That trademark appears elsewhere on a signpost to the old building. At the new building, there are signs of recent looting, with a path leading back to the hovel.
Multiply that by as many times as you think will be fun.
You can make a concept "map" (rather than a geographical one) by making a circle for each location with a "clue arrow" pointing to other places.
This turns the exploration into a story. The only dice you might want to roll are for picking where they randomly wander to, or to find particularly obscure clues. I can't advise enough against having to roll for the obvious clues. That makes exploration into a boring series of trying to find the next clue, instead of an exciting exploration of a rich environment.