I might be wrong about the CD. Still, I think they want you to be using the latest software, and as you've pointed out they wouldn't be able to fit it into the slick packaging they ship those in (although one of those credit card CDs might have fit).

In the past I think I was more surprised that they didn't include a manual. I don't care what people say, the iPod is not the greatest user interface in the world. I think you could ship a Tivo without a manual, but not an iPod. I would be able to figure it out, but my mom needed something to show her how to operate her new gadget.