To me, the reason most SEO companies focus on the onsite omptimisation is because that's the 'easy' stuff. It may be time consuming if you have 100's and 100's of pages to edit all the H1 tags etc etc but it's a definite goal with a definite end in sight.
With link building, as far as I can see you can go one of two ways, cheap, which from what I've seen is mostly scripts sending automated requests to be included in directories which offer little if any value and I still believe risk you being seen by Google as in a 'bad neighbourhood'.
If you look back to the reasoning behind Pagerank, Sergei and Larry where very much academics. So, they were used to the idea that if a paper was published and of great use that many people would reference it. So, more and more people would reference the works which referenced the original work and so on. Links of the pre-internet variety. In fact when I was at college (in the pre-internet - not prehistoric

) days I used to use books called the Science Citation Index. This and others like it were simply lists of all the times an author had been referenced in other journal articles.
I don't think way back when, the Google guys really thought about the commercial equivalent and how that would differ from academia. And so they translated the citations as 'votes' into the links as 'votes'. What I suspect they never really considered was that most people producing research/journal articles do not do so with the main or even any aim of building up 'votes' through being referenced.
Sorry if this is all rather long winded but I think it's quite important in link building. It needs to be 'natural'. That's why (as far as I understand) Google will still look suspiciously on a site which suddenly acquires rapidly a high number of links.
Matt Cutts has written in the past about link bait which I think is worth taking a look at.
I don't think you can beat 'doing it yourself' though. And there are lots of good ways to get ideas of where to link. I quite often look at competitors link listings in Yahoo and start cliking on them to find ones that we could get a link from, for example.