This works for me on windows 8.1.
Treatid: 1) Run regedit.exe
2) Go to HKEY_LOCAL_MACHINE/SOFTWARE/Microsoft/Windows NT/CurrentVersion/AppCompatFlags/Layers
3) You should see an entry for Gangster.exe. Double click it to edit it.
4) Replace the entry currently in it with
"$ DWM8And16BitMitigation 8And16BitTimedPriSync 8And16BitAggregateBlts Layer_ForceDirectDrawEmulation"
(remove the quotes)
Directly run the game from Gangster.exe in the game folder (don't try to launch from the Gog Launcher). No compatibility options are needed. This fix will not interfere with other programs or windows. No need to kill explorer.exe.
640 x 480, 800 x 600 and 1024 x 768 all seem to work fine.
The Menus are still fubar - but the stuttering and mouse movement are fixed.
On my machine, I can see the menus by Alt-Tabbing out of the game and back in - this messes up the display while in menus so that the menu text is no longer hidden.
[My understanding of the problem with menus is that they are being drawn in the wrong order due to a timing issue - the background is overwriting or hiding the text.]
[This is from Windows 8.1 64 bit with NVIDIA GeForce GTX 760 Graphics card]
Edit: Some grief may be saved by ensuring that "Task Manager|Options|Always on Top" is ticked.