How to know which keywords are best for Google?

Alright, thanks but let me break this down in steps so I full understand what you're saying? When I type the following, you can see the results:

virus repair service in new york: About 7,180,000 results (0.53 seconds)
virus repair new york. About 18,800,000 results (0.46 seconds)
virus cleaning new york. About 11,400,000 results(0.48 seconds)
virus removal new york. About 8,260,000 results(0.55 seconds)

So what does this mean, that the keyword phrase below will be the best one to use?
virus repair new york. About 18,800,000 results (0.46 seconds)

If yes then next question would be what should I look for in the top 10 listings on first page for those keywords results?

To expand on this topic, is it an SEO company's job to analyze the competition and suggest the best keywords for the client or is it always up to to client to suggest the keywords?

First of all, any reputable SEO company should help guide you in the optimal selection of geo-targeted keywords for your business. That should be done by analyzing the relative top 10 competition for any of the local cities/towns which you service. You should not be targeting state wide (New York) based keywords. It's best to optimize your website for one major local city. Peel this onion one layer at a time.

Then, your next plan of attack should be to setup a site blog. In that blog, you can submit 700 - 1,000 word articles each of which targets a smaller scope city surrounding your primary target city. That would be how you expand your net to capture supplemental traffic for an additional radius and secondary city/town list.

Now, regarding analyzing the competition, I like to conduct exact match searches such as
"long island computer repair" and preface that search with allintitle in one search and allinanchor in another. That will help you gauge the competition that is intentionally optimizing for the same cities as you. Now, there is a trick called 990 which lets you get past the deceptive Google SERPs count and drill down to the actual, accurate competitive figures. That is a very important factor. Your objective is to identify the lowest hanging fruit long tail keywords with the best monthly search volume coupled with the least competition. This will establish the keyword foundation for any online marketing strategy you leverage.

The two best tools I like for this keyword/competitive research is the Google keyword planner combined with a tool called AllInScraper.

I believe you should be doing a three-pronged approach to lead generation which combines Craigslist and Google SEO. That combined with the YouTube video marketing angle would be a very scalable, logical and realistic strategy. Feel free to PM me and I can help guide you on all these fronts.

Hope this helps
George