Whee! Physical Gods are exactly what we need...
In fact... Wouldn't it be terrific if, instead of simply becoming Mountainhome with a king, if you work hard enough, you could actually invite a Physical God to come live in your fortress?
Or, better, having physical gods attack your fortress in seige mode, and giving you the ability to chain up someone else's god. I already enjoyed chaining up a Titan back in 40d that was worshipped as a god by humans, and stripping her naked, and throwing her on the other end of a moat with waterfalls for my truly legendary Legendary Dining Hall around year 7 of the fortress. (Cue "Where's your God now?!")
Kohaku, I think I love you. This idea is beautiful, and it needs a thread of its own (this discussion is something of a derail from OP), and/or to go on Eternal Suggestion voting.
Basically, perhaps such megabeasts that might be constructs could be a representation of advanced tech from the past or tools of a god(s) for the purpose of interacting with the material world... This purpose would ideally be procedurally generated, of course.
Glad you like the idea! As for "tools of the gods", there are a few ways I can see to accomplish this. First off, lesser "vassal" gods (keep in mind, the question of precisely what qualifies as a god becomes a bit fuzzy) would do the trick nicely. Second, collossi created by a god might go rogue, either desiring freedom or a cult of their own (or even just getting a distaste for their missions - maybe a colossus assigned to genocide might grow a conscience, or such). As for generated rivalries, the history part of worldgen would likely play a role, though preexisting ones based on sphere differences (or similarities; turf wars?) are also likely. Possibly old rivalries could fade, too: Zeus and Hades team up against Thor?