Updated.
Skills: 9 at 9 ranks
Feats: 3
Okay, here's some SRD critters that seem relevant comparisons:
Ghoul
Skills: Balance +6, Climb +5, Hide +6, Jump +5, Move Silently +6, Spot +7
Feats: Multiattack
Efreet
Skills: Bluff +15, Craft (any one) +14, Concentration +15, Diplomacy +6, Disguise +2 (+4 acting), Intimidate +17, Listen +15, Move Silently +16, Sense Motive +15, Spellcraft +14, Spot +15
Feats: Combat Casting, Combat Reflexes, Dodge, Improved Initiative (B), Quicken Spell-Like Ability (scorching ray)
Jann
Skills: Appraise +11, Concentration +10, Craft (any two) +11, Diplomacy +3, Escape Artist +6, Listen +11, Move Silently +6, Ride +11, Sense Motive +11, Spot +11, Use Rope +2 (+4 with bindings)
Feats: Combat Reflexes, Dodge, Improved Initiative (B), Mobility
Hyena
Skills: Hide +3*, Listen +6, Spot +4
Feats: Alertness
The Ghoul seems a good start skill-wise. I don't see them having Balance, but I'd give them the all the other skills:
Climb, Hide, Jump, Move Silently, Spot
That leaves them another 4 from the Genie's skills. Appraise seems suitable, from their love of treasure. Bluff would reflect their fondness for deceiving travellers. Intimidate would go with their Scare power. That leaves one more. I'm thinking Listen. They don't seem very social, civilized creatures (so no Craft or Diplomacy), and since they don't have any combat-worthy spells or SLAs there seem no point in giving them Concentration.
They do like to pretend to be other creatures though, so they'd need Disguise. I think I'll distribute two "maxed out" skill allotments between Appraise, Bluff and Disguise. There are stories about folks spotting a Ghula's really a monster from their odd behaviour or the sight of a cloven hoof beneath the "lady's" robes, so they don't seem to be
that good at pretending.
Skills: Appraise
6, Bluff
6, Climb
9, Disguise
6, Hide
9, Intimidate
9, Jump
9, Listen
9, Move Silently
9, Spot
9
Feat wise I'm thinking we could just give them the same selection as a Jann.
Feats: Combat Reflexes, Dodge, Improved Initiative (B), Mobility