I have searched something similar some years ago. I chose Zen Cart, a derivative of the well known osCommerce, over the later, because it has more "batteries included", and was a bit more consistent. It can still be a decent choice, even more with the (yet to come for quite some time) next version. We are quite happy with this choice.
Now, we need to control quantity per attributes (color, size), something Zen Cart doesn't allow yet, which is annoying (we have to create an item per size). So I am looking at Magento which is built from scratch on solid bases, modern OO design, based on the reputed Zend framework. It looks very promising, extremely flexible (supporting several shops)... at the cost, apparently, of some overhead, I saw several complaints that it is slow (at least on shared hosts): having a dedicated fast server seems to be a good idea. Now, it seems they work hard on this issue, so a bit of testing on real world might be a good idea (plus it depends on the expected number of visits per day!).
PrestaShop seems to be interesting too, more lightweight. Perhaps a bit more limited. Also evolving quickly, might be worth keeping an eye on it.
Of course, there are several other shops, you might find a listing on HotScripts, for example. From CMS supporting e-commerces to e-commerce modules for blogs! Depends on the needs...