There's two sides to SEO. Primarily, like you said it should be making improvements that help search engines properly crawl and idex the site. On-page SEO is easy in sense, because the best practices are well established.
Off page SEO is where everything gets shady, way too many SEO companies automating link building, dummy sites with all scraped content, article spinners, the list goes on....
I just fixed up a site that an SEO company had been "building links" for over the last year. The site didn't have keywords in the title tags, had tons of duplicate url issues, repeated content all over the place, etc. Stuff like that just blows my mind, seen it quite a bit.Good SEO should be a solution based on what a client actually needs. Most of the time they won't know, so it's on us to do our research and find out. We need to research the niche, the competition, the whole 9 if we wanna actually provide value.