“ 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.”
“ The PCs are stuck in a town with a strict peace policy, the tiniest scuffle can land you years in prison. The town also happens to be a tourist haven, so inn-prices have skyrocketed. The only way the PCs can rest is if they splurge on a room, with their enemy.”
“ A great treasure has been stolen from the Palace and taken to the nearby Temple to the Bitch-Goddess Atrath Klee. The King demands that the party go and retrieve it - the only snag is that the Temple is guarded by potent magic that will kill any male who steps inside. It's just as well that the King has a stash of Girdles of Gender Alteration for just this circumstance.”