Hi,
I don't own the Brood War expansion yet, but I took a look at the Leadership cards, and I'm overwhelmed by how much they change the old factions, resulting in each faction becoming absolutely unique. I think most new players will be a little overstrained by the sheer number of options they and their opponents have (including setup), so I started to make an overview of the "new" factions. Here are two of them, maybe I'll add the other ones later:
Arcturus Mengsk
Just like in the RTS game after becoming Emperor of the Terran Dominion, Arcturus Mengsk doesn't care much about what happens in the galaxy around him as long as he can continue to reign. He has several Leadership cards which help him to win without having to expand much, and to defend himself, or to take back lost territory.
At the start (Stage I) you can choose between the SVC (2 planets), gaining the Star order, or choosing your starting planets. The Star order is especially useful for your defense: Place it as a first order (executed last) in your base; if someone attacks you can use it as a Mobilize order to gain back territory, or to protect your base (-> lift off), otherwise you build or research in your base. It's also useful for expanding, since a build order may become useless if the forces you sent there where defeated. The other Leadership card - choosing your starting planets - additionally allows you to select the first player, which means you can select the player to your left and go last, so you can make sure both planets you choose are adjacent, and if you start on a planet with 2 connections, you will have at most 1 neighbour, who will be before you in turn order, so you can easily block his orders (if there is one).
You may worry about gaining enough CPs if you didn't select the SVC, but with Stage II you can choose to transform 2 non-CP areas into CP areas. Be careful, 'cause if you place them both in your areas it will make you look strong, and other players will attack you. You may opt to strategically place one of them somewhere else, though it's risky (but the opposite is risky, too ^^). Alternatively, the Norad 2 Battlecruiser hero isn't a bad choice, either.
If the game didn't end before Stage III, you gain a military advantage with your Stage III Leadership cards, wether you try to defend or take back your two planets or your CP areas.
The Overmind
The Overmind has only one goal: Assimilate all life forms in the universe. While it's not exactly what you do in the board game, you make the necessary preparations: Grow, expand, spread, destroy, become a dominant force in the universe no other force will be able to overcome - you get the idea.
If you don't go for your SVC (3 bases), there are two ways to begin (Stage I): Start with a huge resource advantage (9 workers, +1/1 to permanent resources), or with better starting units and the great Overmind itself, which gives you a CP head start. Note that you gain a CP for the Overmind at the start of Regrouping phase (before bases / installations are destroyed), so if an opponent wants to prevent you from collecting a CP for the Overmind during the current round, he must use Collateral damage or another ability which immediately destroys the Overmind. In addition, note that ground-only areas are easier to defend when you select an area for the Overmind. While the Overmind's CP bonus is nice, it's inferior to Mengsk's ability to select two adjacent starting planets and to place two CP areas during Stage II, and it won't produce more than a total of 5 CPs (assuming the game lasts 5 rounds), so in the best case it just evens out Aldaris' SVC.
During Stage I, you were offered a resource bonus, now with Stage II you get the choice to execute an additional order per round. The downside? If you don't manage to protect the Cerebrate you have to place with this Leadership card, you'll lose the entire bonus, and go away empty-handed. However, this additional order is placed before all other orders, so you can be sure to execute the last order on your home planet if you fear being attacked (that is, unless Aldaris intervenes). While the Cerebrate isn't immortal, the Ultralisk hero Torrasque which you can get alternatively always returns the next round after being destroyed. As we all know, Ultralisks are good at defending bases, CP areas or Overminds, and this particular one can even be sent to a suicide mission, just to return at the start of the next round to protect a base or the Overmind again (yeah, he respawns exactly where you want him to be)!
Unless you already assimilated all life forms in the entire galaxy before Stage III (or made the necessary preparations, at least ^^), you get the option to immediately (during Leadership phase!) spawn a huge force: Execute a free build order on anyone planet, and then retrieve your workers again!!! Alternatively, you can choose to destroy a transport on each navigation route, but be aware that Tassadar has a Leadership card which allows him to build 8 transports on any navigation routes, which should be considered then, as well as wether he's before or after you in turn order.
...I hope you enjoyed these descriptions (or at least found them useful).