Race
Dragonwrought Kobold
A venerable dragonwrought kobold is near-certainly the optimal answer, or at least the start of it:
Ability penalties due to age do not apply to dragonwrought kobolds.
(Races of the Dragon pg. 39)
That means you get −4 Strength, +2 Dexterity, −2 Constitution, +3 Intelligence, +3 Wisdom, and +3 Charisma, along with Small size and the awesome slight build (count as one size category smaller than you are if it would be beneficial to you), for pretty substantial bonuses to AC, Hide, and so on. The penalty to Constitution hurts, but if we’re being cheesy,¹ you can always take Faerie Mysteries Initiate (Dragon vol. 319) to replace your Con bonus to hp with an Int bonus to hp, ensuring you’ll have plenty.
Note that Draconomicon says that creatures of the Dragon type—such as a dragonwrought kobold—can ignore the requirement of 21st level on epic feats. You still need to meet the other requirements—which may be very difficult or impossible for, e.g., skill ranks above 23—but there’s plenty of epic feats you can take at quite low levels wiht that.
If you want to push the cheese further, you could inquire about the greater draconic rite of passage and/or the loredrake sovereign archetype.¹ Those pump your sorcerer level, but maybe it can apply to your sha’ir level?
Planetouched, Lesser?
Aasimar hit some benefits for you, namely Wis +2 and Cha +2, with zero downside. Player’s Guide to Faerûn includes “lesser” variants that give up their Outsider type in exchange for being LA +0, which is a good trade even if you’re buying it off. Venerable dragonwrought kobold is better, but this saves you a feat and avoids the large Strength and Constitution penalties that you would want to deal with as a kobold.
Genasi are elemental planetouched, which might be more fitting, since genies are from elemental planes (though they aren’t elementals). However, their ability score adjustments are pretty useless to you: fire genasi get +2 Int, but take −2 Cha, and water genasi get +2 Wis, but also take −2 Cha, so that doesn’t really help anything, and the other two don’t touch mental scores.
Templates
Beyond that, you could get more bonuses with LA that you buy off.
Unseelie Fey?¹
Well, actually, I guess there’s at least one more piece of cheese we could apply before getting to LA: unseelie fey. Unseelie fey is a template from Dragon Compendium (originally Dragon vol. 304) that neglects to include its level adjustment in its description. Ordinarily, we’d assume it’s LA − and assume you can’t play it, but the Dragon Compendium write-up includes an example unseelie fey gnome warrior who is listed as LA +0. Ask your DM—the template is plainly overpowered at LA +0, but maybe they’ll allow it anyway.
Unseelie fey offers −2 Strength, +2 Dexterity, −2 Constitution, +2 Charisma—that much, at least, is not unreasonable for LA +0. You’re going to want to do something to avoid being paralyzed by Strength damage, though that’s relatively easy to do or to heal. And you’re gonna want to be very careful about your Fortitude. In addition to these ability scores, you also get flight, a “seasonal” supernatural ability, and scaling DR based on your HD.
Another thing to check with your DM: do HD-scaling template features scale only with racial HD, or all HD? RAW it’s all of them but it certainly seems like these sorts of things were designed around RHD.
As for the Su abilities, summer caress is permanent magic circle against non-(animal/magical beast/fey), and winter chill is an aura that applies a penalty on all saves made by creatures within 5 feet of you equal to your Cha, so pick one of those two because they’re flat-out insane. Obviously, winter chill requires getting close, which you may not want to do, but my goodness is that a powerful effect. Summer caress isn’t as ridiculous, but it also doesn’t force you to consider uncomfortable positioning, and it’s still extremely strong.
Half-nymph?
Nymphs are “usually chaotic good,” which makes an unseelie nymph sort of weird, but then, fey are weird. RAW, they’re compatible, and you can still work in Dragonwrought too, but the order matters: it has to be kobold, half-nymph (must target a Humanoid), unseelie fey (any living creature, changes type to Fey if you aren’t already), Dragonwrought (any 1st-level kobold, changes type to Dragon), in that order. Luckily, feats are officially chosen as the last step in your character, and you’re free to order templates however you like as part of choosing your race, so this order is perfectly legal. You wind up as a Dragon (Augmented Fey, Augmented Humanoid, Reptilian).
Anyway, the only reason we’re talking about this is the ability score adjustments: Dex +2, Int +2, Wis +2, Cha +4. Everything you want, a little more Dex which certainly doesn’t hurt, and it’s LA +2, which is really more than it’s worth but you are planning to buy it off anyway. The rest of the template is minor: low-light vision, count as Fey for Enchantments and using magic items (note you’ll keep this when Dragonwrought makes you a Dragon), and awesome beauty (Su)[mind-affecting, fear], which makes any Humanoid with 30 feet shaken for 1 minute just for looking at you (you can suppress this or turn it back on as a free action).
Saint?
If you want the most powerful template, it’s gotta be saint. I’m largely of the opinion that LA—even with buyoff—is basically crippling, but even so saint feels overpowered.
Anyway, saint offers Con +2, Wis +2, Cha +4 at LA +2—which is only okay at LA +2, but it does hit almost everything you want out of it. More importantly, that’s on top of Wis-to-AC (even armored), +2 to all save DCs, free 1d6 damage against any evil creature (1d8 if undead or evil outsider) that hits you with a natural weapon, damage reduction, fast healing, resist fire 10, immunity to acid, cold, electricity, and petrification, permanent tongues, permanent double-strength magic circle against evil, and permanent lesser globe of invulnerability, and a +4 bonus to Fort saves vs. poison.
On the other hand, sainthood is difficult to achieve. You need to be exalted, which means better-than-Good, and if you’re an unseelie fey, that means you are naturally “always evil.” That doesn’t actually prevent you—“always” doesn’t mean “always”—but it’s a thing to keep in mind. Then, on top of being exalted, you need three exalted feats—they pretty much all suck, but Nymph’s Kiss gives an extra skill point per level which isn’t terrible, Intuitive Attack will help your touch attacks if you ever make any, and for the last, I dunno. Knight of Tyr’s Holy Judgment gives you magical knowledge of the laws in any place you find yourself, which is kinda crazy and fun; could be really useful while planehopping.
Note that while saint has a lot of requirements to become one, it’s less clear that you must maintain those requirements after you are. Nothing really says it’s possible to lose the template; there’s nothing about “ex-saints” in Book of Exalted Deeds that I can find. You do lose your exalted feats if you cease to be exalted, so that’s a hefty price, though again, exalted feats tend to suck, so losing them may not be that great a price to pay relative to taking them in the first place.
Lolth-touched?
It doesn’t really focus on what you’re looking for, but it is one of the most efficient LA +1 templates out there: +6 Str, +6 Con, +4 Hide/Move Silently, and fear immunity. The only reason I mention it is because it can be hard to find that much for that little, and it does undo the penalties of kobold and unseelie fey and then some.
Lolth-touched does imply that you have been, ya know, “touched” by Lolth. That’s a scary proposition in the best of times, and for someone actively involved in planar politics, it could be a problem. Also, it’s really hard to imagine saint and Lolth-touched co-existing, for obvious reasons. Lolth is insane, but blessing an honest-to-goodness saint seems beyond even her.
Half-Janni? probably not
Just for completeness, there is an LA +3 half-janni template in Sandstorm. It’s trash (+2 to Str, Dex, Int, Wis; Imp. Init.; +1 natural armor AC; fire resistance 5; enlarge person, reduce person, invisibility, speak with animals each 1/day SLAs; 1/day travel with a party to the Astral Plane, any Elemental Plane, or any Material Plane for 1 minute/level after which you return whence you came), but maybe it’s fitting.
On fluff
On some level, an actual genie-related sha’ir feels weird to me: sha’irs use genies, they aren’t genies themselves.
And fey and kobolds as power brokers feel pretty right to me.
Fey bargains are, of course, a major narrative trope, and the seelie and unseelie often serve the role of go-between between the forces of Good and Evil since the fey courts are good and evil but not the way angels or fiends are.
And D&D 3.5e kobolds—particularly dragonwrought kobolds—are ripe for so many rule shenanigans that it has influenced their flavor in popular imagination, too. “Screw the rules, I’m a kobold!” is a thing.
So unseelie half-nymph dragonwrought kobold seems not outrageous for what you have planned, lore-wise anyway.
Saint is harder to fit in there, and Lolth-touched is harder still. But those are also less important. Just take care with your Fortitude saves, and protect yourself from Strength or Constitution damage.
- Banned in my games.
Best Answer
Dimension Door, Greater (Spell Compendium p. 64)
Less fancy than the options listed in the other answers and requires a 5th level spell slot (or scroll) each time, but once the standard action has been used to cast (assuming no Quicken Spell / Sudden Quicken feat use) then for the next level / 2 rounds it is a move action to move the caster and other touched creature/s and object/s up to 25' + 5' / 2 levels once per round. The movement does not trigger attacks of opportunity.
Our party had a lot of trouble fighting a vampire wizard who used this spell on repeated occasions.