Whenever I try to play Stone Prophet, the screen freezes immediately upon start up. If I use Alt-Enter to make the screen smaller, it unfreezes and I'm able to play, but as soon as I go into fullscreen mode gain, the picture freezes.

Do other Dosbox based games freeze when you make them full screen?

If you're not sure you have any others, you should have ready access to at least a couple (in particular the two Ultima: Worlds of Adventure games: Savage Empire, and Martian Dreams are free on GoG, and if you like RPGs of this era you'll probably like them too) to try.

If other such games freeze, it's something to do with Dosbox on your system in general (and I'm not sure if there would be a ready fix other than sticking to windowed modes).

If it's just Stone Prophet, then it may be the game or it may be a problem with the Dosbox configuration that ships with it; try downloading and installing the "vanilla" Dosbox from www.dosbox.com (or your Linux distro's package manager) and mounting the Stone Prophet folder within it (i.e., using the default configuration that comes with Dosbox). If it still freezes in fullscreen, then something's wrong with Stone Prophet specifically; if it doesn't, then GoG has misconfiggled something in the Dosbox configuration file, at least for your system.