Here's an answer from a slightly different perspective.
Personally, I would love it if the theme handled all of the SEO issues itself, instead of an external plugin. But whenever I build a custom theme for a client, I include the All in One SEO plugin even though my theme is already packed with SEO goodness.
The reason is because my clients aren't always tech- or SEO-savvy. Having the ability to change title formats across pages, or meta description tags on each page, is something they want (even though not many actually use it in practice). It also saves me the work of adding custom fields to the WP admin to surface this kind of functionality, which is really nice.
(There's also the peace of mind it gives to certain clients. Completely perceptual, but hey.)
The Google XML Sitemaps plugin, on the other hand... that's one piece of functionality I wish was bundled with the WordPress core.