I was faced with the same dilema as you a while back.
Having considered the choices, I opted for Zen Cart. Now, don't get me wrong, there are some 'terrible' looking Zencart stores out there.
If you are willing to but some effort in, (that means researching, reading the ZenCart forum) you will be rewarded.
The Zencart community is excellent for assistance and best of all, many of the modules are free.
I am not a graphic / website designer. I was simply a guy that wanted to start an online store without paying anyone.
http://www.reefbay.co.uk
Those initial cost savings can make all the difference for a new startup. In the end, I came up with a store that doesn't look too bad in my opinion. Of course I could have paid, 'professionals' to create graphics and content and it would look better.
For me, this is the first step on the ladder. I'm really impressed with what Magento has to offer, but I'm still taking my time to learn it. Magento will be the second phase of my store (and I may need some additional dev help with it).
Back to the free opensource modules; I have automatic submissions to Google Shopping products, reports on abandoned carts (I have already converted some lost sales with this), SEO friendly URL's.
With Photoshop and Illustrator you can easily come up with a logo and some banners for your store. For mine, I drew a palm tree by hand, scanned it then, mapped vector paths around it.
There are plenty of free tutorials on the Internet showing you have to create various effects etc.
Security patches must be kept up to date with Zencart (and all other packages).
Now, this may cause some people issues with ZenCart- you need to be able to use software such as Beyond Compare (a bit of sofware that helps you compare files for differences) in order to apply these patches if you have made your own modifications to the basic Zen Cart store.
Quick point on the automatic installers such as 'fantastico'. You are better off learning how to do your own manual install for Zencart (dead easy). Automatic installers are not going to help you when it comes to applying security patches (as they won't know how to merge updates in any files you have over-ridden).
Most webspace hosts provide you with cPanel, which is a 'user friendly' interface - so you don't really need to get your hands dirty with Linux.
I guess it depends on your budget, and to a certain extent your ability to pick up new technology / skills and apply it.
With regards to payments, I use Paypal. The payment gateway is built into Zencart and very easy to use. There is an add on module for Sage Pay (written by a very helpful guy on the ZenCart forum) which I think is around
£50.
If you do choose Zencart and need any pointers, I would gladly assist (based on my own experiences).
I hope I have shown that you don't need to spend a fortune on getting an eCommerce store up and running. I don't do 'web design' or anything related professionally. I just want to share what the Open Souce community has to offer new startups.
All the best.
Al