HoMM3 HD is a mod (add-on) for the game Heroes of Might and Magic 3.

With 32-bit MMX, fullscreen mode is technically a windowed mode, so if it doesn't run in fullscreen, windowed mode won't help either. And it's definitely not related to Windows 7. What the problem is, I don't know.
Heroes 3 runs fine in Linux under Wine, and even better in Windows, any version will do, as long as it's not older than Windows 2000.