First, try the standard things if you haven't already: set desktop color depth to 16-bit (65,536 colors), rename avi folder so intro movie doesn't run. BTW, does the intro movie and main menu get split too or just the actual game?
What are your system specs (esp. video card type, OS, DirectX & video driver versions)? What is your desktop resolution & color depth (e.g. 1024x768 16-bit color)? What resolution are you running HoI at (set with HoI_settings.exe)? Have you tried running with different resolutions?