I liked the random Maps in Age of Empires.
Or other RTS.

Imagine Civilization without random maps....

This really makes the replayability much greater.

using Random maps in 3dGS, need either a model-terrainlevel approach,
or using flexible map-entities.
Bsp block-levels are of coures fixed.

And in a random map, it is not about making every element random.
It is more about making the structure of the map random
You could do this by aligning a variety of ready made
sublevels into a bigger one by randomly placing them.
The main work is to make the sublevels work together with
randomly placed other sublevels that are attached.
(choosing the right entrances).

Random map yould be done. But there is no general sollution.
It really depends on the gameplay.