It's easier to list the fixed elements than the randomly generated elements. Below is a list of all map layouts that are fixed. The presence of all dungeons not listed will be fixed, but their actual structure (as well as the structure of all levels not specified within a particular dungeon) will be randomly generated.
- The world map's basic structure
- The structure and primary denizens of all towns or "peaceful" areas, both in the world map and in the Caverns of Chaos.
- The Stone Circle, the Water Dragon's Lair, and the Quickling Tree are all single level dungeons that are fixed in design.
- The Pyramid, the Dwarven Graveyard, and the Bug Infested Ruins have all of their floors fixed.
- The last level of the Tomb of the High Kings, the Darkforge, the Rift, and that mysterious cave in the middle of the continent.
- The Temples are fixed - they always have the same structure, but they only take up half of the floor they are assigned to. The other half of the floor will remain randomly generated.
- The last 3 levels of the Caverns of Chaos are fixed in structure.
- The actual dungeon level they are found on varies, but the Big Room, the Animated Forest, the Eternal Guardian's room, the Casino, and the Bunny Floor all are fixed in structure.
In addition, you are guaranteed various items and events to occur - the availability of all quests, and all items that are associated with those quests, is fixed. All of the above fixed maps will always feature certain features that will always be the same, including treasure and monsters. However, in all scenarios there is still random generation going on, so you can end up with more than just the base layout.
Past that, several of the other dungeons will still have fixed encounters, usually in accordance with a quest. As well, certain dungeon elements (such as vaults) will have a fixed structure to them, but are randomly picked from various possible layouts.
You can read up more on these elements at the ADOM Guidebook, though keep in mind it's highly spoilery. Any area that doesn't contain a map is going to be randomly generated. All elements that are fixed will also be pointed out in the respective points that they can be found.