I'd recruit a spy for every city, then recruit and send at least a couple of spies to any enemy city on your frontier. Then, if you like, recruit and send spies to every friendly city on your borders.. Then, recruit and... well you get the point.

Espionage (coupled with assassination) is always worth it in the end. Much more so than diplomacy.