Hi Ouji
You asked "Is "link building" or lack of it my main issue?". It certainly sounds like that is the case.
Good search results require that you page is both relevant and authoritative. Making changes on page can only effect how relevant that page is. Sitewite changes can redirect what authority you have towards key pages, but you need to build authority to rank in competitive areas.
Building authority (largely) means building links. If Google doesn't know whether to trust your site is will never really be able to compete against those that it does trust.
However, having taken a (admittedly rather quick) look through your site I think that your site might be at a disadvantage in that you don't seem to have very much in the way of original content: Most of the section pages seem to recycle the same few snippets and then the detail pages seem to be largely empty.
There are certainly many ways to "punch above your weight" in the results. However the goal of search engines is to serve up the best page for any particular search. If your site is way off that mark you are always going to be swimming upstream.
I'd start by trying to write original text on every page then adding 1 really strong piece of content that other local sites will really want to link to (then make sure they know about it!).
