1) SEO is harder today than it was in, say, 2000, just like the App Store is more competitive than it was at launch. That is a long way from non-viable, though. There are recent, high profile, successful startups like Mint or OKCupid where SEO was a core traffic acquisition strategy. (OK, you will not be as good at SEO as OKCupid, but you can be as good at SEO as Mint is. They're in an uber-competitive market and found a spin on it such that the skeeziness in the space worked in their favor, because most people in consumer finance are trying to sell you a credit card and Mint was trying to save you money by, ahem, selling you a credit card.)
2) Links >>>> everything else, with regards to ranking for head keywords. Happily, startups are in a great position to get links. BCC has a couple of hundred in five years -- a YC startup can pick up a couple of hundred by launching. AirBNB practically has a hundred from PR coverage in the NYT. A single well-executed link bait or viral sensation seeded with your hundreds of linkerati friends can really, really move the needle.
3) You can still dominate large portions the tail of the keyword distribution through superior execution on your content strategy. Is this the tactic for all seasons? No, if you're just doing brand arbitrage against the same 400 New York hotels that every other person with a phonebook has access to, this will not lead to dethroning established competitors. If, on the other hand, you're finding unconquered frontier and settling it, you win by default. Can I give yet another plug for services which do not target twenty-something white and Asian males and, instead, which target the need of underserved demographics? If your primary competition is Demand Media you should ROFLstomp them for most of the keywords you actively target. (And learn from their model for scaling content creation up.)