People should take into account the limits of the WE when saying this stuff. A good story is nice, but frankly, most people on here arn't even close to being a professional writer. Half of them can't even type gramatically correct english. So, for me, a story would be nice, if its good. But, if you are just doing a story because everyone says you must have one, please, put your efforts to something else.
Also, another peeve of mine, don't use a cinematic to stare at some guy talking to you for 5 minutes. Cinematic sequences take away the control of the player, and force them to watch something. They shouldn't be forced to watching blizzard's crappy mouth animation repeating for 5 minutes while you give a back story for why I have to go save the king's magical cat. This would be better accomplished by displaying text to all players of the conversation and a quest log addition. Nice, quick, and simple. And I don't get bored and want to commit genocide on the map maker for making me read 3 paragraphs of unimaginative text over a 10 minute interval.
Another thing: Unique game systems. These are probably the hardest to implement into War3, and are what is majorly missing from rpgs. People seem quite content to use the regular rpg hero leveling system blizzard gave us. I, for one, am tired of getting skill points when I level up and having 3 stats, str, agil, int to work with. It would be interesting to see a system where you could advance Max HP, Max Mana, Int, Str, Agil, Armor, and Damage (maybe even speed and attack rate) using a stat point system. It would of course need to be balanced out to work right, but I don't think it would be that difficult to make, and allow greater customization of a character.
