Another suggestion, put some bonuses on imperial government and/or create more governments, like totalitarian or even better, communism where walls have ears, so spy on me if you can! Make spying easier on civs that have democracy or star democracy, and make planets with low morale declare independence if you change government from star democracy back to imperialistic... Make it very likely that your other planets join them if you suck as a leader even if they have high loyalty (maybe they are not loyal to you, they are loyal to their species). Make information warfare very powerful against "your planets". Oops, getting off topic...

I have a suggestion brad, why not instead of destroying nullification agents when they are used, have them protect that tile from further spies until removed by the player? There's nothing more annoying to me than to nullify an agent on my manufacturing capital one turn, only to have another agent back there in 3 turns.