I like to make spies as soon as I make contact or even before if creative. If creative I have more for them to steal as a non-creative, I can wait longer.
If your have no -spy or traits that hurt spying, you should be ok, if you do not delay on researching Tele Training.
I normally will go to N. scanners quickly and get the tech that boost spies in all cases.
Once I get a planet (other than the primary ship building or researching one) to were all structures are doen, it ill just make spies for a long time. I want 4 spies vey soon and then I want to put some out to steal. If I am creative, I will not bother stealing, if I am a tele, I will put the spies on sabatoge instead of espionage.
Later I often put any planet that just finished it final build to make one spy before going to trade. This keeps spies coming in until I get a ton.
One other thing I may do is to use the Darlok picture to prevent them from being in the game.