I've mentioned this in other threads, but I did a lot of researching on this when launching my own store, and the one that turned out to be the best was OpenCart. It's based on a MVC architecture which is easy to understand, and creating templates (if you know HTML and a little PHP) is not hard at all.
There's a few features that are still missing (wishlist, store credit, layered navigation, etc.) but those things are supposed to be coming in the next version 1.5.0. The documentation is also a little lacking, which will hopefully be remedied in the future. It's still a solid package right now, and it's my cart-of-choice.
I played around with it a bit, and liked the interface and everything you could do with it. It's definitely impressive. When I researched it, however, numerous sources said it's a resource hog, and will slow down if you have a lot of categories or products. I don't know if that's changed since I looked at it a few months ago you could ask about people's experience and store setups in the Magento forums.