https://bugs.winehq.org/show_bug.cgi?id=3930
--- Comment #68 from GreatEmerald pastas4@gmail.com --- So, this is pretty silly, but for HoMM1 specifically, there's a fix... You just need to install the official HoMM1 patch 1.1 (the intro screen shows it as 1.2): http://handbookhmm.ru/nwcomputing/download/hw9511.zip
Here's the background: HoMM1 uses WAIL (Windows Audio Interface Library)/MSS (Miles Sound System) from RAD Game Tools for its audio (at least the 8-bit one). The unpatched version of the game used an old WAIL version, and the patch updates it to MSS from 1997, as well as updates Smacker. In the Smacker release notes, you can see some things of relevance: http://www.radgametools.com/smkhist.htm Specifically, 3.0 g and 3.0 r (which is what the patch ships) fixes deadlocks and race conditions.
So with the patch, the game starts, the intro cinematic plays, the menu works, you can see high scores. But trying to launch a game causes it to freeze still.