As an example, let's take Yelp. Yelp has carved out a serious niche for itself in the user review market.
What if you thought you could do it better? How would you make traction in that market? Everyone knows and uses Yelp. How could you get people to use your website instead? How do challenge a company that is so far ahead and entrenched?
Other examples of one-company markets are facebook, google (yes I know there is bing and yahoo, but seriously, who uses them?), amazon, ebay, even wikipedia.
How does a late-comer compete with these companies who made good use of their "first to market" advantage?
In all of your examples, the companies weren't first to market. They came along as an unknown upstart and took out the leader in the space by doing it better. Take Google for example, there were lots of search engines before them, including Yahoo, but they had a better algorithm and designed a solution that scaled better, which allowed them to come up with better and faster search results than anyone else.
If your solution is really better, and you get your name out there, the market will find you.
When you are second to market, it can be advantageous.
It still boils down to who emotionally moves their customers more. All the sites you listed are good examples of people who distinguished themselves in different ways and attracted their users on an emotional level.
Facebook - Exclusivity
Google - Relevance to the user search
Amazon - Reliable, easy return, fast shipping
All of those companies evoke a stronger emotion in their users.
When entering an established market where there is at least one other player, there are several ways to acquire substantial market share. To name a few that immediately come to mind:
1 Provide for unaddressed need
Every market represents consumer need and it's a very rare company that can answer every customer's needs.
Example: Google hopes to build a strong cloud-based business providing email services to businesses. However, business MIS takes a very dim view of relinquishing that much control over critical infrastructure. One critical consideration is how secure the comapny's data are in the hands of a third party. One way to compete with Google for this business would be to offer a cloud-based email service where all data were strongly encrypted while in transit and stored on external servers. Google could offer such a service but doing so would remove Google's ability to advertise since they wouldn't be privy to and so would be unable to leverage critical consumer behavior.
2 Develop better emotional engagement
There are so many options here it can and has filled several books. Donate 50% of all revenues to charity, pledge to offset all carbon emissions, provide custom labelled products ("affinity" credit cards), etc. The key here is to identify characteristics with which customers can identify.
3 Integrate with external resources
Build a model that allows customers to integrate the services you provide with those of other providers with which they have an established relationship. Integrate Facebook's profile management with your cloud-based email service to cut out email SPAM, allow users of your microblogging service to integrate with existing geo-presence and mapping services, etc.
Other possibilities: simplify complex features, amplify underpowered features, undercut price, provide better (any) support, etc.
These are all ways to build presence in existing markets but none will be particularly effective without clear, proactive and effective market communications. You can always offer a better mousetrap but if no one knows about your product and why it is better, you're doomed.
You have to find a need that those other companies don't provide. I know, that's really hard but there is something that Yelp, Facebook or Google don't do. That is how you get a stronghold in the marketplace -- find a niche that the big guys aren't doing.
Once you have the niche, then you can expand from there.