I'm having the same problem, but the game lags always. There is a lag even if I just move the cursor on the Adventure Map. The lag disappears if I move the cursor on a black (unexplored) area.
Perfectly smooth if I lower resoltion to 1024x768. But I'd rather play on highest.
See here:
https://www.gog.com/forum/heroes_of_might_and_magic_series/heroes_of_might_and_magic_4_homm_iv_slow_animations_on_1280x1024/page1 I'm going to try the other solutions suggested
EDIT:
Sucess! Lag disappears if I disable all settings in NVidia Control panel as per this post:
https://www.gog.com/forum/heroes_of_might_and_magic_series/heroes_of_might_and_magic_4_homm_iv_slow_animations_on_1280x1024/post21 Let me see if I can narrow it down.
EDIT 2:
As per this post:
https://www.gog.com/forum/heroes_of_might_and_magic_series/heroes_of_might_and_magic_4_homm_iv_slow_animations_on_1280x1024/post29 Changing the power management mode to "Prefer maximum performance" made a huge difference. But I'm still getting the occasional annoying lag on Adventure Map, and I assume it will only get worse on battles with many enemies. So I'll try changing other options if I can.
Still, maybe this will be good enough solution for you.
EDIT 3:
OK, changing the power management
and switching Vertical Sync Off seemed to have solved my lag problems on the Adventure screen (and in combat). So far. I'll see what happens with heavy combat with many units.
Either way, if you change these, remember to create a separate profile for HoMM4 and change it for this game only. So that it doesn't affect your modern games, for which it's much better to keep the mode to Adaptive, and VSync ON.