One issue with Demigod is the lack of randomness which leads to games with little variety : battles happen at the same spots, players buy the same items, in the same order, etc... Once the overall best strategy has been found, it's just repeated ad nauseam.

So one way of breaking that trend and monotony would be to introduce randomness.

First, how would that work ?
At the start of a game, every random element would be initialized with a seed.
First difficulty : since DG isn't a server-client game, the seed has to be computed independently by each client, and the same result achieved. My suggestion would be to use as parameters game ID + participating players ID.
Second difficulty : a different system would have to be used for single-player mode (game and players ID unavailable).

There also should be a way to input the seed manually, in case players wanted to replay a particular setup. In the same way, the "rematch" menu should allow the option to keep the same seed or not.

Next, what should be randomized ?

Flags
Flag types should be randomized, except for portal and trebuchet flags.
For maps with no base artifact shop, the algorithm should ensure that one of the neutral flags has the artifact shop attached.
Non-neutral flags should be symetrical.
Option : also randomize flag number. For some maps (like Cataract), there's not much leeway. But for others (Brothers), additional potential flag placements can be determined.

Towers
Now, that would require more work...
First, determine all potential tower locations. For some maps (Brothers, Mandala), there aren't many to add. For other maps (Cataract, Crucible), there are quite a lot of available additonal locations. Then, for each location, assign the available tower types.
At game start, each location would randomly get no tower, or a random tower.
Difficulties :
- some areas (like citadel) shoudn't be devoid of towers. Several possibilities : make some tower locations non-random, randomize per map area instead.
- we'd need a way to see fortresses not yet on the map. Maybe pressing Shift would show fortresses as an overlay, with linked towers.

Normal items and artifacts
Normal items (gauntlets, helms, armors, boots) and artifacts should have random stats and price.
That should be based on weight tables (armors more likely to get +life and +armor bonuses) defining ranges (both for abilities and prices), so that completed duds (+100 life, cost 7000gp) or overpowered items wouldn't be rolled. On the other hand, there shouldn't be too much attempt at normalization : if no item with +life is rolled in the 50-3000 gp range, that's fine. Time for a different strat. If two items are rolled with similar stats, but one at 1500gp, the other at 3000gp, that's also fine. The second shall be used for stacking purposes.
Some items would have to be renamed, like Boots of Speed, since they wouldn't be guaranteed to get according stats (but don't bother with random names, that'd be a waste of coding effort).

What might be randomized ?

Consumables
Their price could be made random.
A game where health potions are dirt cheap and teleport scrolls cost a leg would certainly play very differently. But that may need more testing (don't want to turn the game into unwinnable battles).