While development time and cameos/easter eggs are all fine and dandy, I'm not sure they should really factor that strongly into a discussion over timeline placement. After all - and I realize it's dangerous bringing one of the most infamously convoluted timelines in video game history into this discussion - Wind Waker was developed before Skyward Sword, but that doesn't mean Wind Waker takes place first.
Now personally, I've always thought of Sonic CD as taking place after S3&K, mainly because of the progression of Metal Sonics. Also I never played it when I was younger, so I'm not as well versed in all the minor details of the game. But the way I see it, since the Metal Sonic design from CD is the one Robotnik now uses the most, it seems likely that Sonic CD takes place the latest.
However, while scrolling through the thread I did think of a good argument for CD taking place between Sonic 1 and 2. Robotnik builds Metal Sonic in Sonic CD, but it gets destroyed. After his plan to take over Little Planet didn't work, he gets the idea for building his own spherical space fortress from scratch, which becomes the Death Egg. In keeping with the grandiosity of the Death Egg, and possibly because he didn't expect Sonic to actually get that far, he built a much larger and bulkier, and silver, Metal Sonic to guard the Death Egg and
get lattes. His resources are mostly focused on the Death Egg so he doesn't put a lot of effort into it (plus he knows there are no rings on the Death Egg, so why even bother?)
After the Death Egg crashes, Robotnik has quite a bit of spare time on his hands, so he builts the much sleeker, but still quite tall, Mecha Sonic. He only sends this robot out, however, after he has already re-launched the Death Egg, almost as a last ditch effort to stop Sonic from hijacking the Death Egg again.
So Sonic CD could fit before the Death Egg saga, but personally I've just always thought it was after.