Are you running Vista / Win 7? If not ignore me . . . =)
You have probably already done this but . . . did you right click the game shortcut, click properties, click the Compatibility tab and check "Run as an administrator" Also, try the Win 98/Win ME compatibility mode. Disabling visual themes and destop composition on the same tab might help as well.
Certain resolutions don't work well on some systems. Go to the Arcanum install directory and find the HighRes.bat file. Right click and "Run as an administrator" an set it to a standard res such as 800 x 600 or 1280 x 800 instead of 1280 x 768 and see if the problem goes away. If so try using other standard resolutions until you find one that works on your screen without the stutter.
If the alternate resolutions don't help, use the HighRes.bat file to uninstall the High res mod and see if the problem is fixed. If the HR mod was not installed as and admin it can cause some odd behavior. You mentioned uninstalling the HR mod so . . . just make sure you run the HighRes.bat file as an admin every time.
If you installed everything as an admin, including the mods, there is no need for a reinstall. If not, reinstalling everything as an admin may help. I would also suggest turning UAC off during the install and installing in a directory outside of Program Files, especially on Win 7. Make sure you backup your saves first and uninstall the game followed by deleting any directories / files remaining under Program Files\GOG.com\Arcanum. I use C:\Games on my Win 7 system.
If all else fails, take a look at the Arcanum support page
and open a help ticket with GOG support. . . =)
Edit: If you are running a dual core CPU; did you try setting the affinity to a single core? Are you running an AMD CPU?