The figures looked more or less human. And they were engaged in religion. You could tell by the knives (it’s not murder if you do it for a god).
—(Terry Pratchett, Small Gods)
The PCs are sent with a diplomat to another country to protect him and do his bidding. There may be some espionage, rescuing, downright bullying, etc. Could make a nice medieval, special operations background.