Storywise...look, anyone can claim that x would be better than y, story is inherantly subjective, but all I can say is that Mengsk with SoK status was a story told when he had...well, SoK status. WoL and HotS are a story of (among other things) how a man who could fight and win an empire couldn't hold it, that while Mengsk is a great tactician, he's not a great ruler (insert Robert Baratheon reference here). Both these statements will no doubt be disputed, but all I can say is that I liked Mengsk in WoL. One of the reasons I liked him because it showed what I'd suspected as early as when I read Liberty's Crusade. Mengsk is someone who loves to work towards something. He works as a prospector, but gives up his big hit to lead a rebellion. He leads that rebellion to victory and gains an empire, but squanders his rule. Mengsk has always been a general first rather than a ruler. In contrast, Valerian has always been a ruler rather than a general (in as much that he hasn't accomplished military feats that come close to emulating his father). To segway a bit, Mengsk is sort of a dark mirror to Raynor, in that Raynor has always operated on the need to fight for a cause (CMC, MSCC, SoK, protoss, RR), and even after the Dominion topples, goes on to help rebuild human civilization. Raynor wants to fight for something, and will fight for another good cause if the previous one is accomplished (overthrowing Dominion), deemed unachievable (taking out Kerrigan) or deemed morally bankrupt (SoK overthrow of Confederacy). Mengsk will also fight for something, but lacks the moral compass to work within his own achievement, or change tune. Think of how Mengsk reacts to his own citizens as the images Shadow Archon posted. The tragedy of Mengsk is that he knows how to fight for what he wants, but doesn't know how to keep it. Heck, even Juliana was arguably a "conquest" of sorts. People have complained about Mengsk ruling ineffectively in WoL, but to that I can only say, "that's the point." (similar thing with Kerrigan's WoL persona, but that's another matter). Mengsk knows how to rule in some aspects (e.g. the propaganda game, as I mentioned), but not only can he collapse in that (see post-Blitz) but it was a game he was already playing with the SoK. That Mengsk so quickly squanders relations with the UP and KMC (see I, M) even before BW, and how willingly he results to the use of force, shows what kind of ruler he is.
But like I said, subjective. And no doubt that's going to be disputed too.