You definitely need a decent storyline - that's what keeps me hooked and wanting to play the next mission. On the other hand, some people felt that WC4 was on the storyline-heavy end of the scale - you might as well just watch a movie. And with what some people have done extracting the movies, you can do just that!