Have you tried other screen resolutions ?

If the game is slow in 800x600 too, then you probably want to conclude that this is the result of an incompatibility

Have you tried running Homm4 in any compatibility modes?

Also to address your 'space' issues you could just install games to an external drive.

Detlik: I don´t know if it´s your problem, but when I played HoMaM IV first I think I had similar problem. And the cause was too big swap file. There was some error that swap file during the play was bigger and bigger and bigger... I had to quit game (that deleted swap file) and run it again.
But when I runned it last year (not GoG version) this problem wasn´t there. I runned HoMaM IV with both datadisks installed. And may be you could find some patch for that.