Registering with Google Places seems to give a free good quality link for a website for a local business. Are their similar other other free local listings for which every local business should be listed?
If you're for local rankings, the standard has been BOTW local, Yahoo and Bing (not sure how the Yahoo/Microsoft deal impacted this) and Yelp. In terms of going beyond the general local listings I always start with the local citation finder (http://www.whitespark.ca/tools/local-citation-finder/) no affiliation I just love the tool. It's a free tool that looks at local competitors and generates a list of local places your competitor are listed.
Are you listed with DMOZ? This is the industry standard directory so I suggest to give it a try. It takes a while to get listed and you need to be approved to be listed. With other privately owned directories (free or subscription based) it depends on where you are based, how good their setup is and I guess how high their page rank is. I know that isn't helpful but a good directory today could become a bad one tomorrow.
Based on my experiences, if you get a good listing with Google Local Business/Places then it will be hard to find a better one. If you are hooked up properly with Google Places you even get pointed out on a Google Map for local searches. Can you beat that?