I think that HOMM2 is the best in the series, with fantastic CD soundtrack as well.
I run some DOSBox stuff here in CentOS7 too and I don't have this problem. I don't know how Wine installation has any effect on this, perhaps you're running the game by invoking the .BAT in wine which then fires up DOSBox?
Anyway, I run them directly with my specific DOSBox .conf files. Setting that I can think of that may have any impact on this problem are:
Fullscreen resolution. Mine is set to monitor's native, 1920x1200 in my case.
Output mode: I always use openglnb, which uses OpenGL w/o bilinear filter. Overlay feels slightly better color-wise, but in many cases has a problem with sound stutter when mouse is active.