You can try old version of Smacker (3.0) to compress AVI in SMK-files, suitable for Heroes III:
It's here
But don't use Bink compression for audiostreams in SMK-files (that may cause problems, use Smacker compression only).

Or you can update your Bink, Smacker & Miles dlls in Heroes III folder to play videos, compressed with new version of Smacker:
Try this (mss32.dll, v6.1c; BINKW32.DLL, v0.5b; SMACKW32.DLL, v4.0e).