I think you should take advantages of anything you can get your hands on. CDBaby, yeah that's good. It's nothing to hand them about 5 or so CDs to make marketable product for you. And then you only have to give them 1 (I think) if you just want them to rip it and distribute for you.
Mp3 sites like Soundclick and myspace.com are good too because that's free marketing for your products.
Don't also forget the mom and pop shops too, but you may also want to shop around with some of the majors too. I know Sam Goody does local bands on consignment. I knew some Best Buys who did that too (but that was years ago).
If you know html or flash or have access to someone who does, get your own website done. Most people who know a little bit would settle for a decent but fair amount of money. I've done a couple of sites for people in html for just a couple of hundred dollars. Even though it's done on a free site, that gives them the option as to whether or not to pay for more space and domain names. My site is on freewebs.com but once I get the money I should make of selling a couple of beats, I'll go make an official site.
Point being said...use your brain and your resources to help your music.