Yeah, your guess is spot-on. Lemmings (amongst many other games as well) uses the trick of switching palettes mid-frame to effectively work around the 16-color limitation. Specifically it does so on the level preview screen to allow the level preview on the top to use a separate palette from the bottom. This requires the graphics emulation to be line-by-line rather than something more coarse-grained.
Based on various
threads found by Google, it looks like vgaonly mode has line-by-line emulation turned on, but for whatever reasons the default "super vga" mode does not, which is why you get the messed up colors with the default emulation settings.
It used to be that IIRC, before version 0.73 of DOSBox the default was different and more akin to the "vgaonly" mode of 0.73+, so for some time the default settings work fine for Lemmings. But looks like after 0.73 you have to change to vgaonly, since the default changed and new default not compatible with what Lemmings does on the preview screen. I've long done that on my own computer as I saw that thread about the setting in the past, so I forgot it was needed. Some people may also have never upgraded DOSBox to a higher version given that issue. It's fair to say that the problem is indeed widespread nowadays for new DOSBox users, given what happened.
I guess it'd be good to create a sticky post on this board analogous to the ones kieranmillar already created for L2 and L3 on DOSBox. Even though I think Lemmix or NeoLemmix are far better options for L1, there may be nostalgic reasons for a user to prefer the DOSBox way.