What is the justification for the nobility? Some appeal divine authority. In one world however, being of noble blood really does elevate you above the common rabble. By virtue of magical aptitude.
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.