800x600 is a 4:3 aspect ratio, and widescreens use something like 16:9 aspect ratio.
If you want it to use the entire screen you have to select a wide-screen resolution, (such as 1280x720 or 1920x1080), or you will get the blurry mess or black bars.
Personally, I much prefer playing in 4:3 for WC3 and use black bars, no problem for me.