The Sega CD version is entirely uncompressed. The graphics and gameplay data in Sonic CD are about as complicated as the data in the Genesis games, but the Genesis games are only a meg or two because they're heavily compressed. There are also the intro and ending videos, which are also uncompressed. Video compression has come a LONG way since the early 90s. I've played plenty of DS games with FMV intros far more impressive than Sonic CD's, and they don't seem to be having any issue storing the game as well.DS cartridges are measured in megabits, not bytes. The largest size I have seen is 512Mb, or only 64MB. The Sega CD version, even with music *completely* removed, is 116MB. So no, it would not fit. At all. Heck, I was wrong in saying it would fit even with the music compressed.
This isn't saying it wouldn't be kinda difficult for them to fit it all in, but writing it off as impossible is just wrong. If they really wanted to they could definitely do it. The reality is that they don't really want to.