My first question is: what, exactly, is randomly generated in Daggerfall? IE: Dungeons, Towns, Monster Spawns, Loot, Houses, NPCs, Quests?
To be honest very few things are procedurally generated during the game, but they used a worksation at the time to pre-generate all dungeons and towns. Some were later tweaked by hand.
Secondly: Are things generated randomly when a new game is started, or has everything been pre-randomized when the game was originally coded? If everything is randomly generated when a new game is created, is it possible to have a completely different world?
Side quests are generated during the game. Daggerfall quest engine is capable of linking dungeons dynamically to quests. Npc can be created with a random face and class and placed anywhere on a vacant house or a dungeon. Items can also be generated and marked as quest items or belonging to a certain npc. Dialog lines can be given to npcs dynamically.
The good thing about this is that all these things are garbage collected, that is free from memory, once the quest ends which is very awesome.
Finally: If everything is random, does that mean there are no leveled lists? So am I just as likely to run into a dungeon of rats as I am to find a dungeon full of Daedra? What about loot? Is it leveled, or completley random as well?
Loot is leveled and random. Merchants inventory is leveled and also random. It's the same with dungeon occupation. Leveled things depend on many factors. You can get some really back luck and enter a dungeon full a ancient vampires and daedra with a low level, but this rarely happens and only in side quests which are repeatable. Dungeon monsters are usually leveled around the players level and depend on the dungeon type and region of the map. Giants can be easily found in the Wrothgarian Mountains and Giant Scorpions on the desert areas. It's possible to find the occasional over-powered enemy like an ancient lych and you may also find a weak rat or bat if you are high level.
You can also find the occasional odd place like in the game you mentioned. These places are catalogued in this site:
http://www.jceason.dircon.co.uk/dagger/dfgprov.htm
It's amazing this site is still up, after all this time.