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 adventure can take place in a slightly shifted reality, where everybody has a totem (an animal guardian). The totem should be chosen randomly and not by the player, it is ok if "Gorflin the Large," a gigantic and aggressive barbarian, has a mouse for a totem.
These totems will assist the characters in small way. It is up to the characters to determine how to get the assistance; the animals won't solve mysteries for the characters only supply the clues. The character may even have a dream where his or her totem actually speaks to them and reveals some sort of clue.