A Djinni disguised as a human? Only works if the PC's don't have access to True Seeing or similar... Few class levels in Wizard or Beguiler and he's both thematically appropriate and (hopefully) effective. If he's human, then still, beguiler or wizard with School Focus - Illusion. If you want to have soemthing particularly odd, have him specialise and bar Conjuration and Evocation. After all, why would a Sultan need such spells?

Doppelganger or the Chameleon PrC if you want him to have that... morphic quality, but I'd shy away from this in an Arabic/Desert campaign