i have tested and worked with virtuemart, tienda, hikashop and redshop.....also there are bridges for other cart sripts
However, lets focus on native joomla solutions.
In my expirience Virtuemart is the best free joomla cart, as well as Tienda, but Tienda needs to mature a bit more than it is now. When you need a freelancer for virtuemart, you will find them everywhere, that is a big plus.
Redshop is very powerful, but a bit pricier,...to me personally very daunting to maintain, and bit heavy script....built on old Virtuemart core, but improved in every possible way.....low flexibility from support on forum, but lots of joomlers use it.
Hikashop is powerful as well, especially Business edition, very straight forward, has much better price than RedShop, and their forum support is very good....i am surprised why isn't this cart more popular among Joomla community.
Other non joomla option could be Prestashop and Opencart.