Don't waste spies
Have you ever noticed that sending spies against some empires is almost useless? I have, and when you have a large empire it doesnt matter how big your empire is, your spies just arent any better.
Having a large empire does not effect your spies at all in any way; nor does it affect your ability to recruit them faster. However, the trick is to use your spies in the most efficient way.
Sending spies against Cybernetics is almost useless, because of their strict rules due to their high Opressometer factor and their tight grip on their populations. The Saurians are not an easy target for spies either; nor are the Geodics. Spies in the Harvester ranks are easily killed also; dont bother there either.
For the Icthytosians and Ethereans it is a whole different picture. Spies are easily sent in and out, although you will still need a high degree of luck to do some damage.
My advice: Dont bother at all with espionage against foreign nations. It is a pain in the ass to be continually managing them and it is better to be on the safe side and leave them at home, defending from foreign spies.