To be the extremely odd man out, I plan on implementing them as bards, here's why:
1. The relationship of Sha'irs to Genies was very specific. They were not your patrons nor were they your ancestors. Rather you used the ancient accords established by the lawgiver, you charisma, and your trained ability to see through genie trickery to negotiate privileges from them including your familiar and then your spells. Which fits with Bard or Wizard and better with Bard cause of the Charisma bit.
2. Historically, Sha'irs were closer to Bards than anything else.
3. In Play, one of the major advantages of Sha'irs was the flexible spell list that borrowed from different spell sources. Of the 5e classes the Bard most closely parallels that component in its own list and, in fact, has a sub-class that includes list-pillaging as a feature.
4. Bards could use a tutelary spirit/divine muse/familiar based sub-class with a heaping healthy dose of tricking/bargaining powerful spirits into service. Beyond Sha'irs that's a fairly common trope for performers and bards in folk-lore and fantasy generally.
5. Sha'irs always seemed a little cannier and more schooled in life than other arcane casters and the 5e bard reflects that. Also, it sits in the 5e leader space, and I think boom-oriented with a minor in leader is a good Sha'ir space.
The only real problem I see is that the bard picks sub-classes at 3rd level - though that annoys me about the bard sub-classes generally since I can't really see 'lucking' your way into being a skald over a lore-master in the same way you might develop an affinity for either the nature or vigilante aspects of being a Ranger.