I imagine that Gaius would have acted very, very differently if he'd been in contact with Lahabrea much earlier than we saw. Otherwise why sit on Ala Mhigo for ten years feeling that the primals couldn't be dealt with? Why let Nael convince the Emperor that Meteor was the only reasonable option left? Why accept being treated like a failure and assigned as Nael's personal attache?
The earliest I can fathom is when Gaius turned on Nael and shot down his airship. It would imply that Lahabrea came to him shortly after he was torn down by Cid in La Noscea and capitalized on his helplessness and rage at being relegated to Darnus' lapdog. However, I don't think that's the most likely scenario. When Gaius finally decides it's best for the Empire if Darnus does not succeed, thus quietly helping the Alliance undo him and retreating to Ala Mhigo, the only new information he seems to have is that Nael isn't right - that he's been touched by something and deceives the Emperor.
I think Lahabrea came to him right after - when Louisoix cut off the seventh rejoining. The ARR Echo of the Battle of Cartenau suggested that Lahabrea was sure that this is it, baby. Why come to Gaius before that? Once the whole "phoenix" thing happened, I think Lahabrea figured - welp - needs moar chaos - and pulled Ultima out of Gyr Abania's basement knowing that Gaius would be the most likely to embrace gifts of extraordinary power in such a way that he'd immediately use them to wage war.
If Gaius was acting in service to the Empire (as far as he was concerned) when he let us take down Darnus, I assume contact with Lahabrea was what encouraged him to immediately go rogue and invade Eorzea alone, swiftly setting the stage for Ultima's appearance. After all, the Emperor was starting to fall ill and claimants to the throne were getting anxious... if ever there was a time to prove his worth...