I recently tried the beta of Heroes Of Newerth and it was very fun. Not being a Warcraft 3 player I was completely confused by the mechanics and gameplay, but I was able to go a few rounds online.
The best part, hoewver, is that they are developing a native Linux, Mac and PC version. Other than some configuration glitches, on one quirky machine (three heads, 5760x1200), it ran just fine on the two systems I tried.
I hope this bodes well for Linux gaming in the future.