It's all about WHAT you need done. If you're looking for one like you see on TV (Gun Smoke/American Guns) that can basically build you anything you want from scratch... that might be hard to find. A lot of them here can custom build a rifle as you want it using parts off the shelf or some dealers (Dark Storm) who can fabricate/cut out their own pieces... so far i've found the gun shops I shop at have been able to handle all the basic stuff i've thrown at them (stuck bolts, stuck sights, sight installation, cleaning, painting, builds, etc...)
I have never had a good experience with a gun smith. to be fair I have only had 3 experiences though. Gunsmiths ruined a colt 1911 I had and the finish on one of my shotguns. My third experience was when I called a gunsmith and asked him to convert my NYPD DAO sig p226 to DA/SA and was quoted something like $300 plus parts. I did it myself in 20 minutes for $60 worth of parts (thanks youtube).
Maybe you should consider doing your own work with online help. But if you really think you need to hire a gunsmith, better check them out before you trust them.
I had South Shore Sportsman work on a 1911 that was previously converted to 9mm. I had them convert the pistol back to it's original .45 configuration. They also repaired a Ruger revolver that had a timing issue. Oh, almost forgot, they also replaced a stubborn rear sight on one of my 3rd Gen S&W pistols. I broke my sight removal tool and those guys were able to remove the sight without doing any damage to the pistol, or sight.
I'll always go to them first, before anyone else locally.