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.
In the harbour of a major city a large and terrifying ship made of human nails docks. Nobody seems to inhabit this ominous vessel, someone needs to go on board and unveil the mystery. In comes the PCs.