Your right, it's randomly generated. On some save games in Daggerfall, I've had a lot of areas in Hammerfell appear as a snowy forest. The desert is usually very gray and dull looking, not desertish. In my opinion, High Rock and Hammerfell being in Daggerfall doesn't really count because everyone has a different view of the provinces and nobody actually knows what they look like.
Its pre-randomly generated, like how Oblivion operated. Its not random as everything remain the same, imcluding every dunegons, landscape, and town one went. If anything that is ramdonize, its the quests and dialogue, both heavily complexes compare to todays games.
I know about Redguard! Never played it, but videos and all that. (: I hardly think it counts, though. Like, there was a spinoff (I think for cellphones) that came out in 2004, and that took place in Dawnstar, but lo and behold, glorious Skyrim, seven years later!
Lets be honest though; Redguard depicted Cyrus as one of the most badass hero in the whole series. He also made http://www.imperial-library.info/content/lord-vivecs-sword-meeting-cyrus-restless and http://www.imperial-library.info/content/origin-cyrus. Hes a freaken jedi, I tell ya.