They’d proabbly be Alliance.
Far more story potential with them there than Horde.
Void Elves are literally just goth / defected Blood Elves (Highborne) with a major connection to the void, and the most likely ally to be able to help them with any sort of needed redemption arc. If there’s any group that’d either reach out, or be reached out to, it’d be them.
Kul’tiran have legends of mermaids, and a connection to N’zoth. Easy kinship there once the Naga prove their allyship.
Highborne Night Elves are also something that the game’s been sleeping on for ages, and they could take a focus on introduction stories. (Let Mordent do things?)
There’s also that whole “renewal” thing they’re supposed to be dealing with right now. Nightborne, the original “highborne as a unique race” request also wound up going Horde, leaving the original request still fulfill-able with a twist in Naga.
There’s also the fanservice matter of WC3; Illidan is a Night Elf, and the Blood Elves are now Alliance via Void Elves. Having that whole trifecta all on one faction would be a treat, and a morale boost the faction desperately needs after years of wasted fanservice potential. (…or worse.)
Blood Elves also booted their own kin out of the country over void magic. They aren’t going to ally up with a different void race simply because Kael’thas was allied with them briefly at one point. They were the only group that’d likely connect them to the Horde, and uh… yeah, not anymore.
The other races would have little to no interest in them, especially with how the Vulpera were almost rejected, and especially with how the Naga we keep running into are still hostile to everybody.
Also, no more neutral races.
The Alliance needs something that’s actually requested and unique after Kul’tirans and Mechagnomes. Two worst represented races in the game by a landslide.
Horde get Ogres in exchange. Last two major RTS races that aren’t playable. They’re a perfect match.
Double also,
Legs don’t matter. Mechagnomes and Dracthyr exist for transmog, and they’ve already been depicted riding mounts sidesaddle in Hearthstone.