So what is left? Glorified mod_rewrite hackery?
/edit: That's not a flame. I'm just interested what non shady SEOs do. The last time I looked into SEO it was all about rearranging your HTML so the spider would get to the content fast. And to put nofollows on your links to get the juice flowing the way you wanted.
But this wasn't that complex that it justified hiring an expensive SEO company. Sure, they all did that link building stuff too - but as noted above to me that's shady (it was mostly about spamming digg-like sites with top 10/5 articles).
A lot of this should be covered by any half decent site but as you may not find surprising, most sites out there don't know or don't bother.
Shouldn't that be the aim of any website? Being interesting so people like the site and talk about it?
While there are a lot of technical pieces to SEO (that go beyond mod_rewrite hackery, as you put it), most legitimate SEOs spend as much time on the marketing side of the equation. There are a few legitimate link building "tricks" out there, but most SEOs doing a good job at link building & social activities are focused on creating worthy content that ranks well in search and gets attention on social media sites.
BTW, nofollowing links to "sculpt" the way PageRank flows through your site doesn't work anymore - nofollow now "evaporates" the PageRank rather than forcing more of it through the other links on your page :)