Following your suggestion I just changed the output=opengl to output=draw under the dosbox.conf file and all the stuttering video went away.
Nudiustertian: Core 2 Duo 6400 on a Radeon X1900 GT here. It's definitely not the detail; the game is no problem at all for modern hardware. I only experience slight lag/stuttering during the FMVs, which is because the game switches resolutions when playing those. I have no in-game lag.
Try the following adjustments in dosbox.conf:
* under [sdl], output=ddraw. This works best for most configurations. Other things you can play with: fullscreen=false (to see if full-screen output is the problem), under [render], setting scaler=normal2x forced to force 2x resolution (the game runs under 640x480, so that's 1280x960) to see if things run better when you're closer to the native resolution of your screen, frameskip if you really have to.
* under [cpu], core=normal, cycles=2000. In-game, you can use Ctrl-F11 to increase cycles and Ctrl-F12 to decrease them. Play around a bit to find the sweet spot.
* under [mixer], rate=44100 or even nosound=true, to see if the problem is with the sound emulation.
For more detail, read dosbox_README.txt, it contains a lot of information on the settings. You can't break anything by playing with them; make a backup first so you can restore defaults if you render the game unplayable.