The Elder Scrolls: Arena (1994)
Which game lets you visit the provinces of Morrowind and Skyrim? And Hammerfell, Elsweyr, and all of the other provinces on the Elder Scrolls continent of Tamriel. Why, it’s the very first Elder Scrolls game, The Elder Scrolls: Arena!
The vast land area is, of course, only possible via the magic of procedural generation. While parts of the game (such as the main quest dungeons and the basic city layouts) are fixed content, much of the rest of the game (such as shop names, sidequests, other dungeon layouts, NPCs you meet in the street, and so on) are procedurally generated.
Whiterun looks a bit different, five hundred years before Skyrim.
You can, in theory, walk from town to town, asking the locals where the nearest dungeon is, but this quickly highlights the weakness of the game: though the world is vast, the generator isn’t quite sophisticated enough to differentiate it and you’ll end up using fast travel quite a bit to skip to the next interesting place. There’s not enough context to keep the different places separate in your head. Still, for 1994 this is quite a lot of content, and you’ll likely only see a tiny fraction of it.
Randomly generated dungeon, partially explored.
The dungeons can be a bit sparse, with more dead ends than treasure. It can also occasionally be clever, when the water canals, pits, secret doors, and other hazards combine in interesting ways.
One thing that helps overcome the weaknesses in the generator is that you can acquire very powerful spells and tools that let you create and remove walls, levitate over pits, let you absorb magic, and just generally let you turn the glitchy nature of the game against itself.
(Arena, due to its troubled production, also started that other Elder Scrolls tradition of lots of bugs. The currently available version has patched the worst ones, but it’s still not perfect.)
Bethesda released Arena for free online a while back, so you can go download it from the official site: http://www.elderscrolls.com/arena/