I feel like I see a different Legio than everyone else. I have played many games with Tahlan and in all of them I've just ignored legio. They usually get killed by other in factions in my games, in fact.
I've never seen that. What I have seen in about half the games is that one of the first invasions they do is the capital planet or key heavy industry/military planet of some faction or other, and they always, always win. Which takes that faction right out of the game, bam, bye, done, before they had any impact on the game at all. And when Legio does that to several in a row - which I have seen happen - I do have to wonder what exactly the mod author is really trying for.
For "player challenge", they need to be tactically difficult / interesting and strategically resilient. I won't speak to the tactical side of it - I have managed to get to the point of knocking out the Lucifron or Melchiresa star fortress within the first year of play, although it takes focus and a fair amount of cheese, and the more I work at the problem the more I find ways of optimizing my approach. It's made me get better at the game and I'm not complaining about that.
I wouldn't mind - I would be rather in favor of - a steadily increasing drumroll of threat. But the curve should be a lot shallower in the absence of the hard mode trigger. I see nonstop failed invasions of Lucifron by all the NPC factions and that's totally fine - it's strategic resilience. What I do mind is that Legio goes straight for the throat and wins, right off the bat, every time. And Legio conquests don't often get taken back. Which turns the game into a sort of Kohr-Ah death march, except it starts immediately rather than being an endgame phenomenon.
If I want to play a game of just me vs Legio, I can do that; I don't need to include other factions. If a player does include other factions, that should mean more than just buffering the time it takes Legio to swallow everything.