What do you do when a huge online company (as dominant as say Google, Apple, Microsoft etc in their respective niche) has a big feature that's been lacking in their very popular product, and your startup is based on this missing feature, but the big guys decided to add this feature to their product?
It's usually not a good strategy to build a startup based on the "missing feature" of a huge company's product because what's happening to you now is what I think always happens. Big companies pay a few guys in a room to watch the market, detect opportunities early, and particularly to monitor startups that are building the "missing feature".
So if you fail, you'll have learned a lesson: don't do "missing feature" startups! Bad business strategy in my opinion.
As for trying to differentiate yourself based on pricing/service/new features/execution, I think it will not work. It works when you're competing against other startups; that's when execution makes the difference and that's where the "missing feature" strategy works. In your case, the bigger company probably has an established customer base and a significant marketing budget; the network effect and branding carry a huge weight in customers' buying decision. You'll fight hard but as time goes on, you'll start to lose confidence because you won't be moving the needle much. And in the end, guess what will happen.
Now, since you've already got a running business with a team in place, you could try to innovate and create a new business altogether, or you can continue fighting the mountain. Your choice. Big companies have the advantage of easily adding the "missing features" and startups have the advantage of easily shifting business models; play where you're strong.
Just like we've seen with the smartphone wars, ideas are pretty common, it's the execution of those ideas that makes the difference between iOS, Android, and Windows Phone 7. You need to figure out how to execute in a way that plays to your strengths as a small, lean company.
You can throw in the towel or you can fight back. However, you can't go toe-to-toe with the big guys. This means you can't charge the same price for the same service, and legal action, even if you have a patent, is probably out because you don't have the deep pockets to see it through.
But you can fight back asymmetrically. If the features and/or functionality are the exact same, differentiate yourself in other ways. Maybe by charging less, maybe by providing better customer service, maybe by adding features more quickly. If the features and/or functionality are different in a valuable way (or you can figure out what to add to make it different in a valuable way), then play up that feature. Regardless of what you do, pick a course of action that plays to your strengths as a small company.