Well, I followed all the good advice and had a blast fooling about with assassins. I'm playing Scotland (H/H all battles auto-resolve), reduced denmark to a single province then used it to as a training camp for assassins (maybe like Afghanistan under the Taliban). With the 8* spies in place I soon had some 5-8* assassins, who then went off to ruin cities with sabotage.
Assassins only really get good once you've got at least a major assassins guild. The HQ gives you 5* base.
They're bit fiddly if you're running a major offensive, but very amusing. Killing a poor innocent 0* princess made my leader into a seriously dreadful guy.
Of course its also expensive to rehabilitate cities once you've wrecked all those upgrades.