I managed to track down the full set of soundtracks for Lemmings GBC on youtube:  https://www.youtube.com/watch?v=lySsBKMzLxY  The video notes lists the times in video for each track (note: not in same order as in the game).

Overall, the music honestly sounds like it was arranged for one of the more primitive sound hardware from way before even the time of GB regular, like for example the Sinclair ZX Spectrum Colorful Arty linked to (except I feel like even that version still did a better job).  Perhaps the company that did this port (which I'm fairly sure was a different company from the one that did the NES and GB ports) had only dealt with consoles with more primitive sound hardware before doing the Lemmings port?  I almost wonder if they just reused music from some other game that they already made/ported.

I checked Wikipedia and it confirms that GBC is backwards compatible with regular GB games, so it stands to reason that it should be capable of at least the same music you'd hear on the regular GB version.  The blame thus lies solely on the company that did the porting for the GBC version.

I have in fact played every level on both the NES and Gameboy (regular) ports (through emulators), though to be honest I don't remember much about their music.  They were more or less what I had expected, the same familiar music from versions like DOS, arranged to work with the limitations of sound hardware on those consoles.  I guess there's a charm to it if you are into these kinds of old-school "chiptune" kind of sound.

Comparing with the Gameboy (regular) version on youtube for a few different tracks, I think I actually like the Gameboy version better than the NES version, though I can't rule out possible variations in recording quality being a possible biasing factor in the different youtube videos I listened to.

That link you posted Nessy (this one is also kinda bad) sounds like a very bad version of (Titus the fox). Yeah that does sound bad that one.

For me I would have to go for the atari st one as that was the one I grew up with. My favorite one would have to be

https://www.youtube.com/watch?v=TDscrCFwdFo