I've been working with some SEO guys to optimize a few of my client's sites on our multisite install. Based on previous problems I had with Yoast's WordPress SEO not properly rewriting titles on even the default twenty eleven theme, I went with Infinite SEO. However, I find it lacking in both Meta optimization and the automatic linking features. The automatic linking features can wait, but if I'm going to use this, I'll need some additional Meta optimization features soon, if at all possible:
The biggest thing is that All In One SEO can do that Infinite does not, is rewrite some of the Meta data automatically for you. It will rewrite titles, autogenerate descriptions, and use categories and tags (depending on your selections) to do it. This makes your site a lot more optimized, without all the work from the user. Please consider adding this kind of functionality, especially if you really want it to be an attractive plugin that brings in new customers/subscribers.
I'd just stick with All In One SEO, but unfortunately it causes problems on multisite.