Shopify? Wordpress woothemes? What is the best option?

Many others will disagree with me but except in certain circumstances I stay away from wordpress for e-commerce sites given the security issues with wordpress.

If you have a single (or couple) product with multiple options (colors, sizes, etc), Shopify is actually a great match and if you look at the successful Shopify stores, they tend to be in this vein.

Before you start working with an SEO company, get the site up and going and get all your low hanging fruit off your plate (email marketing, social media, comparison shopping engines, etc). While SEO companies can be useful I find they understand e-commerce less than traditional informational websites and as such, can be of less help than a company or individual who is used to building e-commerce websites.

If you can give us more details on what you are selling, we can give a little bit better advice. Is it a single product, multiple products, what options or variants, etc. How are you shipping (real time shipping, flat rate, free)? What functionality do you need the cart to have?

I use Woocommerce for all my ecommerce stores. Very quick and easy to set up and add products. As for the security of Wordpress, there's tons of security plugins to take care of security just fine. No monthly fees is the benefit I like the most. Once you have the theme and extensions you want, that's it except for buying a domain and hosting.

Go with a hosted solution, always.

You'll never have to worry about backups, expansion, out of date software, growth, traffic spikes, etc. What's better, a plugin on a platform that loves to break plugins every time there's a major update, or a cloud-hosted solution that backs some of the top brands in the world and can scale to any size company/any amount of traffic?

eCommerce is so much more than how the site looks and feels, it's about what you can do with the data AFTER the sale. Hosted wins every time.