They're not perfect, but I think the warbands in the core rulebook are pretty well-balanced - so I'd suggest a mercenary band of your choice, Witch Hunters, Possessed, and Skaven.
Beastmen are the only non-core warband, but they are still official and decently balanced, so they could easily be substituted. They are quite tough and fast, but have zero shooting.
Skaven have a bit of a bad reputation for being powerful - they do start strong, with 6 heroes, lots of models, and cheap shooting. But their weaknesses become evident after a few games. Since they were one of two warbands that came in the original Mordheim box, I think of Skaven as one of the most classic Mordheim warbands, so I always like to see them in a campaign.
Possessed can be a little tough starting out since their heroes are so expensive (and get more so if you buy a lot of mutations), but they can become very strong if they survive early. It might be a little rough for a total newbie to start with them. With the Shadowlord being such a centerpiece of the lore, they're good from a story perspective.
For Mercs, I'd stick to just one of the 3 as they have similar choices. Any of them work. Also was included in the original Mordheim box - I've never been in a campaign without one mercenary band, so for me, it's not even Mordheim without them!
And I love my Witch Hunters of course. They're a lot of fun with rock-hard henchmen, cheap and nasty wardogs, the prayers of the Warrior-Priest, and heroes who can pack strong firepower. They're also great fun from a story standpoint, and they're the perfect foil for a Possessed warband.
I'll echo Cygnus that for narrative and multiplayer reasons, it's better if you have two "good" warbands, and two evil ones. That said, I don't think you can go too far wrong with any mix of what you listed. They are all reasonably balanced and bring a variety of playstyles to the table.