I don't like to build spies in the early game. On borders fighting units are a deterrent against invasion as well as loyalty-lifters, and all you need is a fort. It might be the way I prioritise my building building, but I start building spies around the same time my trade routes open up, and I can drop my taxes. An Orwellian state usually comes into it when I'm bringing the Holy Land into Christendom.