The only method I know to hit all of your marks is to buy CDs and rip them yourself. Preferably buying them used locally or from eBay to make sure the "cheap" requirement stays as low as possible (to offset the effort of ripping).
Actually, the answer (IMO) to both avenues is Amazon. My wife buys music in digital form, and I got her away from iTunes because she found out she couldn't share her music with me (I don't listen on my computer, just in the car, and I have no iPod).
For myself, however, I buy from the Amazon Marketplace. Even with high shipping costs from each vendor I buy a CD from, I can still come out ahead of any local used record/CD store, and the selection can't be beat. I've found albums on there that I've searched for for years, and I'll find them for $3. As long as it's usually in "Good" condition, it's still a rip-able disc, and I get the artwork to boot.