There are very few surprises during the missions and everything is kinda spoiled just before it starts. I would have loved something more on par with WC3 in this matter.
The other issue with the story telling is that most of the 26 missions are just sub quests with little to no influence on the main plot, and their individual plot is not really entertaining (just the Zeratul part was cool, but voodoo guy and hanson were kinda poor plots).
And that bothers me because i think the main plot was actually good (not fantastic because it reamined kinda simple), but in itself it was VERY short for a whole game. If we sum it up :
+ Show Spoiler +
Jim gets artifact, Jim is told Kerrigan will save the universe, Jim is told the artifact will save Kerrigna, Jim go to Char, Jim saves Kerrigan
It is very very short compared to the whole story of games like WC3 and Starcraft 1. Sure these had submissions too but somewhat less and overall a lot more was being told during the game.
As a matter of fact the last 3 missions of Sc2 WoL were really good in my opinion. The story was kinda linear (and you still had to chose between 2 missions), and it was good, good cinematics, the impression to actually work for something big. The feeling is good.
I wish they kinda forget about their massive sub-plots "choose your mission" feature, and just give us something more linear, with a better story and with a few choice here and there. They can keep the fun missions because this was really good for the genre.
I want more story told, and more epicness in it.