Katherine, I don't know what your budget is but my recommendation is to think about having a theme designed just for you. I've tried buying themes before and I've always been unhappy with them. Of course, that might just be because I'm really picky about the way things look and work. :) I always want so much tweaking that it winds up costing more than just starting from scratch. I've had great luck using vWorker.
Raijen, thank you for your input, I will check out vWorker. I had an experience where I used what looked like a nice clean template and found it had hidden links and code I could not change. I wish I had a bigger budget than I do!
I've had good luck with Theme Forest. $30 - $50 avg. Not seen any hidden code (yet). They're pretty easy to customize.
Apart from random, free WP themes, I have a developer licence for Thesis but have deployed it only on two sites. I bought a single instance of WooThemes (Postcard theme, but got two more free in the same deal).
Both are SEO friendly and the pages get indexed very quickly. However, the journey to achieve a customised change is painful in Woothemes. One such annoyance is that every post by default has its links no-followed. You have to check a box to enable links to be followed. What was the developer thinking? Wait, you don't even see this option unless you unhide the "SEO custom fields". The themes are coded differently, so you have to check the forum discussions carefully to ensure that you are not dropping the wrong code in the custom files. At least both Thesis and Woo give you this feature so that you don't mess up the core theme files.
I've got dev licenses for Thesis, Genesis and Headway. They are similar SEO-wise, and I use them all for different reasons. (I've used woo and others for clients, fwiw)
Thesis is very flexible - so if you've got a specific look and feel you need to match or very specific functionality (custom) needs - it may make the most sense.
I like Genesis for the slick, good looking child themes - a bit of tweaking and you can have a nice looking site up and running fast.
Headway I've used where clients want to "do stuff" since it's got an interface they can fairly easily understand.
Woo isn't a favorite, some things they hard code (like dates) which should really be pulled from your wp settings. (although they have some nice looking themes)
my 2 cents. :-)
I have used a free theme for awhile but had to do a lot of code changes to make it look close to what I wanted but has forced me to learn more PHP. Beyond that have plans on starting a second site and looking mainly at Woo Themes, Genesis, and Thesis. Leaning towards Genesis at this point because I can use it on more than one site without paying extra and also the security built in seems to be better than most. As far as custom changes not sure both Genesis and Thesis appear to be able to be customized without having to edit the specific file.
I'm not quite sure if there exists a 'seo friendly theme'
As long as you have the permalinks, post excerpt, categories, tags and the likes set up correctly and a proper flow and functionality of your site's content.
Any WP theme will do the trick and i'm yet to see a theme that has 'actually' helped in improving SEO results. Perhaps the one aspect to pay attention to is how the heading tags are rendered.
Thesis and genesis frameworks are the best theme frameworks available I'll recommend you to look at genesis child themes. Even copyblogger & problogger use genesis.
I, too, recommend the Genesis framework. Nice and clean, and uses child themes as they are supposed to be used. The basic package is pretty reasonably priced.
I'm a fan of Thesis. It's the only thing I've used, but it allowed me to tweak just about anything and it seems to have gotten picked up be search engines rather quickly.
Me too recommend with pageline... its preety clean and also SEO friendly cheer
The best theme should be a theme designed specifically for you keeping in mind your own requirements. There are a lot of plugins available which can be installed for the purpose of SEO. Just look for the best design and compatibility to your existing blog.