I know a couple guys that use Tunecore and love it. It's not that expensive at all.
I would definitely go with Tunecore then find a supplemental distributor that can get your stuff in stores.
For physically getting your stuff in stores check out the following site.
http://www.indierec.com/s-distribution.html#1stop
What's cool is that you can contact stores in the regions you want to sell and let them know were to purchase your music from and they'll get in in stores. This is a huge asset if you're trying to push real hard in a certain market. They also make the hard copy of your music available for purchase on the major online stores like Tower Records.com and such.
CDBABYalways reminds me of a place like soundclick only dealing with real cd's instead of mp3's.
I've actually decided against buying someone's record because the only place purchase it was on CD BABY and nowhere else.