Same here. I have just started to work for a company. My site is about Real estate in India (My Property Stores). And its very difficult to get the site up in Top 10 because of the competition. I am thinking to introduce my Site to PPC. Lets see how things can work with it.
What's the best company for me may not be the best for you. You need a company that really knows its stuff and your market well and that understands your company.
You need to find a reliable company that can backup its results but also that shows that they understand your business and your philosophy (your marketing will not only be affected by your goals but by the way you do business and your principles too).
Marketing is elusive and it is all a matter of trial and error so you need a company that you can trust.
Before asking, do a search... if you don't find the answer, then ask The purpose of this forum is to help others in the community, that's why it's called Sitepoint and not Linkpoint. SP Guidelines - No fluff.
Search on the internet, or ask friends/collegues. It's easy for a company to boast about results and capacities. So if you have a friend or a collegue that has good experience with a company, that's a plus.
And like molona said the post just above yours, "best" is relative. You need to be more specific.