I'm running my PC on my television (which doesn't support such a low resolution through HDMI) Is there any way to force the game to display in a different resolution? even one as low as 800x600?

Yes, 13 years later, but yes it's possible. Use dgVoodoo2. Extract the dgVoodooCpl.exe and the dgVoodoo.cfg, and the dlls inside MS\x86 in the game folder. Double click on dgVoodooCpl and remove the "Disable Alt-Enter to toggle screen state" under DirectX tab, then apply and close. You may remove the watermark too if you want.

Now start the game, press F4 and it will switch to windowed mode. Stretch the window as you like, and then, Alt-Enter to use that resolution as full screen.

It's the only solution I found, it fixes windowed mode and pseudo-"full screen" mode. But it doesn't fix the framerate!