There's no downside to partial views when implemented correctly.
If SEO is important, you do need a separate URL for each page to be indexed and show up in search results. However, there's a way to go around this using the new navigation history framework (HTML5), and some tweaking for Internet Explorer (IE):
The idea is to change the URL dynamically when a partial view is loaded, and to complement this, you design things so that a URL determines the partial views to load, therefore building the whole page just like it would have happened through user interaction.
This pattern allows both SEO and partial views to co-exist in harmony, and allows the user to user the back and forward navigation buttons.
Then all you need is to make all those URLs accessible to crawlers, either through a site map page, a
sitemap.xml file, or by uploading all URLs to Google.
As @TomasAlabes says, there are certain user actions that suggest navigation, and the user will expect a complete page reload. However, even if just a few elements of the page will stay the same (e.g. header and footer), partial views will still reduce network traffic and user wait time.