I'd like to try undeads - which one of the two expansions would you suggest taking? My wife is playing Uthuk.

The one featuring Necromancers: they are really one of the most interesting classes around, and are able to represent pretty well the idea of "undead horde moving".

In general, each box was designed with the idea that units inside the box were able to develop a good synergy with their abilities, so, both should grant you quite a few hours of sheer fun

Yeah, necromancers look great, but are bone horrors and barghests any good compared to analogues?

Yes, they are good. The important point to keep in mind is that Undead armies play differently from Daqan and Uthuk, so, some time is needed to find out the best interaction between the troops and how to field forces. Same for the Elite units, and so on

Terror of the Mists (Necromancers, Banshee, Barghests, etc.) is my favorite of the two, but I didn't have to pick and choose, I got them both at the same time

Either would be great additions to the Core set, but I think it's worth noting that Heralds of Dreadfall includes the same types of units as the Daqan/Uthuk get in the Core set (Infantry, Archer, Cavalry, Elite and Legendary). Terror of the Mists is more similar to the Daqan/Uthuk army expansions in that it offers alternate infantry, a spell caster, etc.

If you'd prefer a little more symmetry in the 3 factions, go with Heralds of Dreadfall. Then plan on expanding those factions with the other army packs.