I guess the most common SEO service web hosts offer are the Google Adwords vouchers/promo codes. I've also seen some offer search engine submission, but I'm not sure if they use a program that they install on their servers and it does this, or if they manually submit your website URL to something like http://www.addme.com/ ..
How do you mean program? Are you talking about a reseller type setup?
With Big Red SEO we've been doing a ton of preliminary reports for people and contacting various businesses. These reports used to take up to 2 hours to complete, but now we've automated much of the process down to 15-20 minutes per report. Once the client sees the reports and signs up, we have a whole new set of reports and systems in place - but much of SEO is by hand. There's really nothing out there for automation of it as each client is different.
You can automate the monthly reporting, tracking of keywords and sending ranking reports - but that's all AFTER you've done the SEO work for the person.
IBP is great for getting initial reports and tracking pages etc. I use it here for some sites. I also use WebCEO, raven tools, market samurai, SpyFu, and SpyFu ReconFiles and various other programs to get views of a site and optimize. I've never found one program to help with everything, so it's still very much a manual process.
Offering monthly reporting seems to be the cornerstone of keeping clients updated with the latest events and stats of their websites and I believe it is the most important aspect of every single successful SEO campaign as they would like to see real improvements happening to their ranks.
All reputable firms are doing this and depending on the packs they sell to their global customers, they would be sending emails reports and PDF documents containing charts and illustrations of monthly performances of their customers websites on Google as well as other search engines.
A SEO provider should be authoritive for marketing strategy of the website. His work starts right from the keyword analysis and assist the developer in choosing the appropriate title, url and meta tags for the site. In the content part he should analyze the keyword density anchor text features and inner page structure.
As the saying goes the well begun work is half finished the onsite SEO process is the crucial for any site and you need to have good expertise in doing that. Following this the off page optimization works are quite common.