Nationwide unrest

[Varyar]

I have noted the same thing. However it might still be because of spies. I played a game as Milan and had big unrest problems in my capital but after a serious effort I managed to rid the town of spies and suddenly all unrest, even that pesky 15% was gone.

So my only suggestion would be to try harder. Gather as much as 5 or more good spies in a single city and wait and see what happens.

[FactionHeir]

Spies usually cause around 30% unrest though, which, while of the same kind, is impossible on island cities because the AI doesn't use boats and as proof you never ever see Rhodes being occupied by the AI even later in the game.
And if Rhodes has the unrest problem too (i converted it to a city btw), and every single city I own does (even those on the far rim of the map far away from any other faction), then I do wonder what this is about...

[Dan.o6]

The AI does use boats, extensively infact. In my current campaign I have seen various armies landing all around the map, and it's not just armies they have transported Diplomats, Priests and Spys aswell.

[Quillan]

Spies cause 5% unrest per point of subterfuge they have. The tax penalty and religious unrest are listed separately with unique icons. Character traits can cause it, but it does seem to be somewhat more widespread than in RTW. A number of provinces in RTW had base 15% unrest and a few had base 30% unrest (Judea, Cilicia, and the amazon homeland plus maybe 1-2 others). In my current Venetian campaign, Venice has none, Zagreb has none, Ragusa has 10%, and the remainder (Bologna, Florence, Milan, Genoa, Ajaccio, Cagliara, Durazzo, Iraklion and Rhodes) all have 15%. There are no spies on the islands, and no governors in any city.