Additional environmental challenges.
I think that many levels in different areas of the game are too similar to each other despite the fact that the locations' descriptions clearly state their uniqueness.
To remedy that, I thought about a couple of additions:
1) Lava flows: outpourings of magma from the core could appear in ToEF but also rarely in random deep CoC areas.
It could be like a very small river, perhaps 5-10 tiles long and random shape (but still continuous, with a clear beginning and end).
It would not be restricted by room/corridor boundaries, bridges built over it would burn (or impossible to be built in the first place), ice would melt when frozen.
Characters immune or highly resistant to fire could cross it, possibly with ring of ice/fireproof blankets to prevent item destruction.
It would be represented as light red =.
Dark forge could also have that between the forges.
2) Acid pools: I'm not sure how it could be tied to the lore, other than through connection with black dragons/wyrms.
It would appear as 2-3 tile wide pool of green =.
It would dissolve bridges, though not instantly.
It could be frozen but character's boots could still be damaged/destroyed (the frozen acid beneath you melts under your heat! your blessed seven league boots...).
Barefooted chars would take damage with respect to resistances/immunities, higher metal boots would last longer if worn instead of leather/cloth/iron.
Similarly to lava streams, item destruction would be immense if swam through, though obviously without possible methods of prevention other than avoidance or leaving items behind.
Characters with acid immunity could swim in it.
3) Lightning anomalies: obviously BDC comes to mind - this could be light blue =.
The shape would be random, ranging from 2 to 5 tiles but connected.
It would of course damage items vulnerable to shock and any living things not immune to it.
Many such random anomalies could be put on different levels of BDC and perhaps also in air temple.
4) Mana disruptions: appear as green =, it would act as magedoom eye draining when stepped on.
Chars with Wi>32 would not only be able to resist it but also to replenish some amount of PP they previously lost (or increase natural regeneration of PP wile standing on a tile, akin to Terrinyo island?)
Placement around mana temple (instead of or in conjunction with pillars around the altar) but maybe also on D50, stone circle or library.
Its default shape could be a ring of varying radius (2-4 I guess).
5) Tectonic fissures: 2-4 tiles long in similar shape to lava streams and water rivers, black =.
Chaos twists reality - both matter and spirit - as it grows more powerful and prevalent.
So, even the very Caverns of Chaos would slowly erode when the malignant energies float through the shattered foundations.
PCs could fall into the fissures without high climbing skills and experience item destruction similar to the rift (potions, scrolls, wands, missiles...), before climbing out or emerging on the level below.
Some of the above extra tile types could also be placed around orb slots to indicate their inert magical power and show how they alter environment (including already existing water tiles).
Maybe the correlated anomalies could spread randomly out after each orb is placed in its respective slot. Thematically proper I think.
Also, all of these extra tiles could have a small chance of appearing randomly, with the frequency of rivers or with increasing DL.
They could be implemented in existing locations such as fire/earth/air/mana temples or provide building blocks for something in the future (volcano?).
The interesting stuff begins when the character is stunned/confused and stumbles into one of the special tiles or items are thrown into them.
Some monsters could be made to ignore some of these obstacles, like incorporeal/flying creatures and anything immune to the destructive effects like respective demons, grues, elementals, dragons, wyrms...
Greater vaults could have these features added for extra diversity, depending on what type of monster was generated inside.
The groundwork for this is already out there so it's not such a huge project - we have blue water and red water with their separate interactions.
The rules already exist that govern the creation of random structures such as rivers so it's just a matter of adaptation.