Mengsk was a fairly reasonable enemy in the vanilla game, and he still is. His Leadership cards are nothing over the edge, and like the Overmind, he is more in the brutal force and may as well try to accomplish his special victory as if trying to go after CP. Like with the Overmind, you want to decide early on. To be honest, you have to.
In stage I, you choose if you go for special victory or not. If not, you take the star-order token. I wouldn't waste a second thought on the option of choosing the starting planets for you. All it will gain you is the envy of everyone else on the board and much pointing on you and calculating how obscenly good your position is if they don't crush you. Good for one-on-ones, though. The star.order is much more interesting: on the one hand, he's a joker, especially nice if placed on the bottom of the stack. If you're attacked, you can counterattack, if not, well, then you build or research. These are the situations where the other poor bastards have to discard orders, draw event cards and help Aldaris to victory. Later in the game, another reason for the star-order may be apparant: you may attack, build or research four times, not just thrice. This can be very important.
In stage II, you need to make a real hard decision. Will you aim for the CP, then you can throw in two more of them on the board. I strongly recommend to sacrifice one of them and place it between to players who have been on friendly or neutral bases of late because they determined their zones of influence. This is no time to be greedy. They will constantly fight over the CP, while yours is yours alone. The other option is to get the Norad II. With that ship, the enemy needs vastly greater numbers than you have to defeat you. At least in the area where this ship is headed.
In stage III, you have two equally weak options: either get one time reinforcements of considerable strength along with the candy of Colleteral Damage for cruisers, or you get all buildings on level 3 and may build like hell in the next round. I think the latter is one of the weakest options in the game and only needed if you have much ressources and few units. Or if you are really uncertain of what is to come, since it is a star-order-extended for one round. The reinforcement thing isn't that strong either. Sure, two tanks or cruisers deal a whole lot of punishment, but they can't stand a comparison to the devastating effect of Aldaris' stage III cards. It's highly situation dependent which of the two you want to take.