Halicarnassus is based on a Garlean folktale that Nero happens to be aware of. The text in her instance summary says she's an antagonist from a classical novel where she rules as the Queen of Dimension Castle. Exdeath's instance summary says he's a villain from an ancient legend and the legend said he is an evil tree that takes the form of a dark mage. Whether or not that is Garlean or not is never specified. Alte Roit and Catastrophe's origins aren't specified anywhere as far as I can tell.
As far as I could tell, Nero has been researching Omega for quite a while by the time he brings it up as a way to combat Shinryu. He's just never turned it on until then. It's anyone's guess as to whether Omega was checking him out the whole time, but I can certainly buy that Nero is the person who's been around Omega the most in "recent" times.
I think Varis is extending an olive branch to the WoL since Zenos' Resonance project failed. Or, not so much failed, but left Varis with no control over people who have the Resonance (as far as we've seen anyway). If it had worked and Zenos had overcome us, then Varis would have had his fake-Echo users to work with (pressure into) taking down whatever eikons there are around. Instead, we're pretty much free of his direct power/influence and that's a situation he probably doesn't want to continue. At least until he manages to get another Resonant up and running...
Speaking of talking down eikons... what eikons/primals are around that Varis is worried about? This isn't like the Warring Triad where Theoden all but said he was absorbing existing primals' power at the end of the expansion and then we spent the reset of the patches dealing with them. 'Cause given the characterization the Scions and WoL have been given so far, we'd probably figure out a way to get to any primal that happened to be out regardless of who the primal is directly threatening. It's not like we need alliances in place to have reason to do that.
I'm thinking that the whole alliance Varis is proposing will be framed like a hypothetical for when a primal is summoned. With the goal that when a primal is summoned someplace that isn't in Garlemald, Varis gets to have some sort of influence on how the Scions deal with the situation. Probably in exchange for not giving the Scions trouble if they have to deal with a primal that is in Garlemald. With lots of fine print for both situations. Having influence on what the WoL can get up to would be great for him.
The other scenario I could see is that there's a lot of primal summoning going on that the Scions don't know about because it's in Garlean territory. And Varis needs somebody to deal with it. And with the Resonance project in shambles, he's run out of options. How the Scions could figure out if he isn't lying is up for debate (his censorship working against him). And who knows what he would do after the situation is dealt with... Thing is, there's no reason the Scions and WoL wouldn't want to deal with that kind of situation even if it was a bad deal.
Also, I don't think the Four Lords are primals from what we've seen of them so far. So I don't think whatever alliance Varis is proposing is about dealing with them.
Speaking of looking at all the puzzle peices and not just the ones we just got, I wonder what the Garlean NCPs on the Prima Vista will think about all this. The entire reason they are in Kugane is because they're running from Varis (well, his policies). I'll be very interested to see if their dialogue changes at all for this patch.