I'm stuck between two WP themes. One says it is highly SEO optimized. Another looks nicer but says nothing but looks cooler. Do they really make a huge difference in SEO optimization even if I add plug ins and such?
Different themes affect SEO, though your plugins, keywording, content quality, etc. will also play a factor. I've used a few different themes but I've found Thesis to be an absolute SEO monster and worth every penny.
The level of Optimization of a theme highly depends on you. If you're good enough at seo you can even make a static html page better optimized than a wordpress page. Out of the two themes just select the one that looks better and the one with which you'd be able to perform better. Leave the Seo part to the plugins and your own knowledge application.