There are many solutions that will fit this request. I think much depends on whether you want more or less support for the software, and how much customization you will need. Nearly all carts need some customization, so finding someone that is good with these tasks (support and customization) is probably more important than the software itself.
I think www.cubecart.com offers a nice solution with their latest version - setup can be done in half an hour and the default skins are not bad at all. Good seo options and and good support forum. Affordable too.