I managed to fix this with WC3's DOS settings. You can run it from Galaxy under "More" => "Other" => "Launch settings". It'll go through some steps, after the Gamma correction test it'll show a screen with some text on scaling. Press "Y" on this screen to force WC3 to use some vieo mode that fixes the problem. Then continue until you get the option to save the settings.
NOTE: the installer forgot the music and sound settings for me, so you need to set these up again before saving. Picking the first "Soundblaster/compatible" with all default settings worked for me (and presumably for everyone since it's being emulated in the DOSBOX). Make sure you set this up for both music and sound separately.