You should definetley consider a plugin that displays x number of random posts on the sidebar. This way your old posts don't become "stale", and it gives your readers more to read about, apart from what is listed on the 'most recent posts'.
I would recommend the Search everything plugin, which enables search on the entire site, not just posts. For SEO, I would maybe use some plugin that tags posts and puts the keywords in the header, there are several of those.