Magento is in a league of its own. It provides every option you could ever want for eCommerce and there are some fantastic themes for it. There are three big downsides:
1, it has a very steep learning curve if all you're accustomed to is WordPress;
2, non free plugins and themes are expensive (extortionately so);
3, Magento lacks drag and drop for widgets, menus and other layout features that are standard in WordPress. Some themes require code edits to remove cross-sale, upsale and other ad images that are built into them; and,
4, Magento has a very badly designed backend interface. It's very awkward to get to grips with.
On the plus side, Magento works well with SSL.
If you use Magento, read the instructions. There is a good list of Magento guides at
http://blog.belvg.com/how-to-start-with-magento.html
Read the instructions for any theme you install into Magento or you will get frustrated.
Magento will work on a good shared server such as those offered by Bluehost and Hostgator until the site gets very popular.
If you need a good WP eCommerce solution, use WP e-Commerce by getshopped. Look in the WordPress plugin repository for extensions to it. You need to pay for authorize.net payment gateway usage and support but the functions offered by the plugin are greater than those offered by other WordPress eCommerce plugins. Next alternative is MarketPress from WPMUDev.
Just my recommendations.