I've found that assassins' skill curves are different than other units. They're virtually useless when you first train them, but as soon as you succeed once or twice they escalate in a hurry. The best way to bump them up at the start is to kill enemy assassins, low level diplomats, or captains of small units. After a couple runs like that they'll be ready to take on bigger fish. Even failing a mission can give them traits and retinue, so keep them active.
My favourite assassin moment was when I tried to get a ceasefire with the briton faction heir, who was alone on their shore. He cruelly rebuffed me, so I sent my burdgeoning assassin after him and succeeded, earning him 2 more stars. Take that, full unit of heavy chariots.
How do you use assassins? Tips or tricks or good stories? Share them.