It's a shame to have to arbitrarily make this tradeoff. There is nothing inherent in saying that apps that desire rich client-side navigation are 100% the apps the DON'T require search engine support.

Google does have a spec for hash-bang URL's to enable both to be present in a single app. Unfortunately, it's clunky and not universally implemented.