Again, I'm just going to say it.. there are very few strategy games which have ever made espionage fun. It's an incredibly difficult thing to get right. Tim Ward touched on some of the issues, but yeah.. there's too much danger of it either being an annoyance, an irrelevance which players will seldom bother with or something which feels unfair.
A great example is Civ 5. The espionage system in Civ 5 was really well designed from the standpoint of the game as a whole, because it got rid of a problem which has always been present in Civilisation games where one player will tech ahead of the others and just end up dominating. Espionage did a great job generally of spreading technologies from the most advanced players to less advanced players. But.. players really didn't like the system. It wasn't fun to use (just assign agents and wait an arbitrary number of terms while random chance determines what happens) and if you were the most advanced player it was incredibly frustrating because you were constantly losing advantages which you felt you'd worked hard to achieve. Sure, you could defend yourself to a limited extent by building certain buildings or counterespionage, but both were still fairly unreliable.
Unless there's a specific in-game niche which espionage can fill in Stellaris, and right now I don't think there is, I'm just not seeing how adding it would be a good idea, even in the above sense of being a good idea in terms of game balance despite not being fun to use.
Long term, I can see some cool stuff being done with espionage. Once the pop, ethic and faction systems are fully developed and fleshed out, for example, I could maybe see a role for espionage in terms of influencing those systems in other nations (funding or empowering factions, for example, or spreading propaganda to increase the attractiveness of ethics) but even then it would need to be carefully balanced so as not to be an annoying griefing engine when used against you.
