here is what works for me in the long run:

1 unit of peasants (slavic warriors if available, or nubian spearmen for muslims) on standard size: the minimum cost for maintaining the minimum 100 garrison required to keep bandits out
1 religious agent (bishop, cardinal, mulla) {keep the faith in line}
1 assassin {kill AI's spies and assassins}
1 spy {pump up loyalty}

some provinces require more spies than 1 to maintain loyalty at 200... (livonia, portugal, lithuania, for example): so, just make a few more for these provinces. spies have no yearly upkeep so they come out to be very cheap happiness maintainers :)