A dark type Pokemon will be one of the best counter to it, and the one I’ll reccomand was Houndoom
This was the set that Cynthia use on her Spiritomb:
Spiritomb (Lv 78) @No Item
IVs: 0 Atk
- Shadow Ball
- Double Team
- Dark Pulse
Likely, houndoom was immune to Will-o-Wisp and resist the two STAB move from Spiritomb. And you could encounter at Route 9 in black which was pretty early.
Instead of Houndoom, Mandibuzz was one of it’s counter, could use a tuant and makes it to be not access to use will-o-wisp, double team and resist it’s two stab move.
So simply, all dark type or could learn taunt Pokemon could get rid of Spiritomb easily.
However, instead of using a Dark type Pokemon, another good way to beat Cynthia’s Spiritomb was that train your Pokemon level higher, seems Cynthia’s Pokemon was like level 75-77, and you could use a Pokemon like level 80 or above to beat her Pokemon.
Guide for beating her other Pokemon:
-Freeze Dry could get rid of her Milotic, Garchomp and Bravery at the same time
-Lucario was easy to defeat, use Pokemon that could learn moves that was super effective to it.
-Electross has a painful speed, use a Pokemon that could learn a lot of strong STAB move to defeat it
Hope it helps!