Tough call. WC3 gets the nod. Though I could vote for WC2 as well. WC2, in my mind, had the best ships (ok, so I like the Epee, sue me) and the best system for dealing with Fighter vs. Capship combat (an Arrow can't kill a carrier with only lasers). But WC3 really pushed the Interactive Storyline.
Honorable mention goes to Prophecy. It seemed to reconnect with the WC1 & 2 style. I got kind of sick of the galactic scope of Blair's accomplishments. I liked him much better when he was only a pilot, prior to the ending of Heart.