Here's a list for you to start with http://business2press.com/2009/02/23/30-must-have-wordpress-plugins/.
Just note the new All-in-one SEO had some issues on my blog. It asked to update database files and it lost the setting for some reason
Mine is ok. When I updated all in one seo, the settings are gone but when it tells me to update my database and I did so, the settings are back.
I've found that All-In-One SEO has been one of the most useful plugins for me. I'm sure many others agree.
WP Super Cache - Caches your blog on high traffic days if you get Dugg or instalinked or something. Title Tags - Custom title tags are essential to SEO.
Below given threads useful to you. http://forums.digitalpoint.com/showthread.php?t=1395718 http://forums.digitalpoint.com/showthread.php?t=1395616 http://forums.digitalpoint.com/showthread.php?t=1400575 DON.
The best advice I can give on fighting spam is to have the Akismet plugin installed and configured. I also highly recommend the register-plus plugin as it keeps down fake registration by robots when you enable required fields and captcha, as well as email verification.I also use Google XML Sitemaps to help google find and index my site correctly. Last but not least is the very help ful All in One SEO Pack. If your hosting company is saying that yoru blog is overloading the server you site may be ready for the WP Super Cache.
If I had to pick just one plugin, it would have to be the xml site map generator. That way I know that all of my pages are being submitted to the search engines. Everything else can fall to the wayside, but I want my pages indexed. I dont care what plugins you have installed, if your pages are not indexed, then your not going anywhere.