Solving hard problems depends too much on creativity and research. I'm not sure I could do that under the pressure associated with a startup. The Google environment doesn't seem ideal either, come to think of it, but at least, I'm not the one absorbing the huge risk of failure.
Anybots is a startup that solved a hard problem, but it was self-funded, right? Would YC have funded them if it had been proposed by a 25-year-old Trevor Blackwell?
Uses some pretty advanced algorithms for planning seating arrangements.
Of course, the real challenge with a consumer product is usability, that intersection b/t your cool product and the folks with the wallets. But, that's where the money is. (Money isn't everything, of course).