Have you thought of spawning lairs?, since the game initalises with dungeons, and they are improvemensts iirc, could not more be spawned during the game when certain techs are aquired, and a number of the next level of dungeons are spawned, or made visable by tech aquiring, i suppose if they are all generated at start, each level requiring a range of units level to enter, say 1-3, 4-6, 7+.
Yes, I just drew up a "to do" list and lairbuilding is about number 23!