Well, I can report I played Warcraft III and a plethora of other games with Wine back in the days. So I am sure (given how Wine has improved) you still can play it with Wine. No Windows required.

>I missed out on Warcraft III the first time around. What's the best way to play the original game today?

The HD remaster is the only official means on Battle.net, but it sucks. I'd recommend just torrenting the original and running in a VM. Plenty of active private servers still out there.