Spies ... I'd have to agree with the comments above, and more. Spies are brilliant! I can't imagine playing without them, and find them the most useful of agents. I'd highly recommend that you tried them out.

First for the loyalty boost in your own provinces. It's hard to hold the more rebellious provinces, e.g. Portugal and Livonia, without them. Using spies in all your provinces almost does away with the empire wide loyalty drop that happens when you're around 50% of the all territories.

Secondly spies allow you to conquer much more quickly, as you can drop the garrison levels in new provinces rapidly instead of tying up an army while you wait for loyalty to improve. My armies always travel with a spy or two, who enter a conquered province on the turn after it's taken if the province has border forts. Otherwise they are killed if they go in on the turn you invade.

Thirdly, spies will warn you of impending rebellions, and identify the leader of the rebellion before it happens. This is another good reason to have a spy in every province. This is most useful with the factions like the Turks and the Egyptians, where you can't marry princesses to your less loyal generals.

Fourth, trying a general for treason, (and succeeding!) when you have a new king is a good tactic. If someone has been identified as the leader of an impending rebellion they will go down. Otherwise pick on a low level low loyalty unit leader. Success increases the loyalty of all other generals by 1. Failure decreases loyalty by 1.

Fifth - well, I've never found that revealing the vices of an enemy general has caused a rebellion for them, but it can be fun to do. I've several times revealed the Pope to be secretly avaricious.

Lastly, they are effective at causing rebellions, given time. A spy left long enough in any province will cause one unless it's already rebel. The easy example is Denmark when held by the Danes. They never build border forts, so you can drop one there and forget him. It might take 100 years, but the rebellion will come. Usually the Danes will beat the first rebellion, but the second one happens much more quickly, and eventually they will be kicked out, or destroyed. That said, I now leave the Danes alone, because they almost never attack me, so will trade with me to the end.

If you get your spy into rebel territories without border forts, like Genoa, Portugal or Lithuania it makes it very difficult for another faction to take it.

As has been noted, border forts are instant death to zero level spies, but spies with 3 or 4 valour can travel pretty much at will as long as they don't stop in a place with border forts for several years.

I start building a spy centre right from the start of a campaign. Syria is an ideal place if you're in that corner, say as the Turks or Egyptians. Assassins produced there get +2 valour.

I do use bishops/religious agents to spy, but my impression is that leaving them in other factions provinces increases the loyalty dropping Blackmailer vice. For this reason I've reverted to spying with emissaries and princesses.

(The Byzantines are great assassinators of bishops. You can see this by making spies and assassins visible in the crusaders unit11 file. It's fun to watch everyone's assassins cruising about, and after a time they start to assassinate each other - and your spies! However, border forts don't seem to work when they're visible, and eventuallly they start assassinating high level generals and kings. Spies also don't catch them when they're visible, so when they go after your agents, bishops etc. there's no way to stop them. So it's not a thing to do for a long time. The Almohads also asssassinate bishops, and I believe this is why the Pope gets "discomfitted" and calls for a crusade against them.)

Spies can level up quickly if somewhere with action, which mostly tend to be border type provinces. They get 1 star at Citadel level, and 2 stars at Fortress level, and moving one of these into a rebellious province will give a noticeable loyalty boost.

As Asai said, Scotland is a regular drop in centre for assassins if it has a port. So are Naples, Valencia and Pomerania. If you restrict the number of ports you build you will catch more. There seem to be many more about in the early and middle parts of a campaign, and they're much more common when starting in High or Late.

I love Halbs and Arbs too - but do you really train units in newly developed territories? I find that I'm always making them in the same places - usually in my homelands where they get better armour and valour boosts from the Master buildings. You might also notice that generally the AI controlled factions only make one of a building type after the Keep level, and train all their troops of that type from that province.

Generally all agents cause a loyalty drop on other factions territory. Sometimes you can walk an agent, like an emissary, across several of an enemies provinces, and if loyalty is low a string of rebellions occur in his wake. Dropping all your agents on Portugal just after it's taken will often cause a rebellion. Fleets also cause loyalty drops even if not enemy, so popping a fleet next to Rhodes will can cause an eruption.

With Naples as the example, you will see loads of agents sitting there. Eventually, if nothing changes, there will be a rebellion there.

So when you've just taken a place, and a string of other factions agents drop in they are lowering the loyalty there. It's not just curiosity. Likewise, you can use your ordinary agents against other factions in the same way.

I get the impression that other factions "don't like" seeing your agents crossing their lands. If you're poking into a normally hidden territory, like, say, Arabia or Wallachia, then often it will flush out another factions "hidden" army, which then jumps into a visible province.

I suspect behind the scenes that there is a table with the attitude of other factions to your faction - a bit like the Senate table in RTW, or the Pope's table in M2TW. Using any agents in their territories probably causes their "attitude" to yours to be hostile - increasing the likelihood of an attack, decreasing the likelihood of an alliance, etc.

Spies are brilliant! :D