The problem with the Hexwraith idea, I fear, isn't that regular civilians are scared, but that people in the know are scared. This is how you get witch hunters and the Greys looking into you. And remember, this is legally dubious magic, as the Golds didn't want credit. I'd be worried about sending off demon messages.
But on the other hands, Hexwraiths aren't evil. They are anti-necromancy things sent by Morr. The people in the know might know that as well. But then they are enslaved by necromancers, so...
So update on new info from this: people in the know
aren't going to be scared (yay). As for Hexwraiths being sent by Morr, that's a no, but they are innately anti-evil, so I doubt they are considered demons.
Regardless, this info makes me not worried about a Nazgul/Hexwraith if we are doing a rider on a horse thing.
In fact, I'm all in on Nazgul:
First, as stated above, I don't think we need to be horribly worried about the Nazgul/Hexwraith problem: it's different enough to those in the know, but also we don't care about civilians getting confused: we are the most liked Wizard in the most death obsessed province, we can tell people its fine, and they'll actually believe us that it's fine (they'll have some reason). We just start a rumor there, and we are good. We might not even have to start a rumor.
Second, we don't want something good for fighting a single thing, but an anti-swarm tactic. This is what we are weak against. Hence as Boney pointed out, a Demigryph is good for killing one opponent, a horse for scattering many:
A horse is good for bulldozing through a group of people, a murderkitty is good for absolutely ruining one person at a time.
Third, I want this to cause fear. Fear is always a good thing.
Fourth, it looking terrifying is good: we don't want it looking human. Because on a miscast, we want to be blamed for letting it get out of control, not siccing it on our allies. And if it looks like a wizard or knight or other ally, people who don't know magic will look at it like a golem we completely control. Making it look like people will cause more reputation damage. I think
@Redshirt Army highlighted this problem?
If we want to go full beast, I think a giant scorpion is the best option. It's very killy, and doesn't waste any limbs for wings that cannot fly.