The biggest issue is the difference between:

SEO=link farming, spamming blogs, generated blogs/sites, etc...

SEO=building accessible standards compliant markup, making it easy for people to find content they were actually looking for, etc...

My gut reaction to hearing "SEO Company" makes me think of #1, even though I know "good" SEO is really just good page development, good content, good use of keywords, etc... As an engineer I'd prefer to hear about standards compliant markup, accessible (508/WAI), canonical URLs, clear DOM structure, and developing content to better serve users: which is really what it's all about.