Maybe instead of a fortress, the Overlord could randomly enter different zones, creating a "Battle the Overlord!" mission. Basically, he spends his time rampaging instead of chilling out away from the action. As a mission, you could really spice it up. Maybe even make the fights different depending on which Overlord you're facing(determined at continent gen, probably, to keep weirdness like the Overlord changing between fights if the player dies or flees).
Maybe the godzilla boss could rampage around a large, mostly flat map while meteors(like those from the Defend Supply Depot mission) rain down everywhere. We could have a lava-dragon type boss that you have to fight in an area with very little land and lots of connected lava pools, which the boss swims between to attack you from, occasionally launching the lava in a spray everywhere. Or some really weird stuff, like a flying fortress style robot boss, which could even act as a multi-stage fight. First you have to get into the "overlord"(which is in the sky, and has tons of turret defenses and flying mechanic monsters), then once you're inside you have to navigate to the core, or mother computer, or whatever, and defeat it in a typical "Shoot the core!" style fight.
If the player doesn't do the mission, have something happen in the zone he was in. Maybe it renews the windstorm in that zone, forcing you to deal with it again, with some sort of "repair the wind shelter" mission?
Or what about different windstorms depending on the overlord? Godzilla gets the normal windstorm, lava-dragon gets a fast acting heatwave that does more damage than normal but can be mitigated(but not removed) by a heatsuit, Fortress gets a lightning storm that instead of doing steady damage randomly hits you with lightning for larger chunks of damage, but can sometimes be dodged.
Either way, the point would be to make it at least look like the Overlord is actively causing trouble, rather than just chilling out, enjoying the weather when the glyph bearer busts in Kool-Aid style "YOUR DAYS ARE NUMBERED, OVERLORD!" with basically no provocation beyond the dude being named "Overlord". And his parents just thought it'd be a cool, intimidating name, you know?