That seems excessively high. There is absolutely nothing special about running that type of circuit that requires anyone special other than that they must hold an electrical license. I'd call around and get a quote from a local electrician. Almost sounds like they're a specialty group and you're paying for lodging and travel from their home base somewhere. Also, I'd call the city/town, or whomever you get your building permits from and see what the price is to add a circuit to a panel. Now, if they must upgrade the panel to support the additional load, that could add up quite a bit, but not if it's simply adding one to an existing panel. It almost sounds like you're paying for a crew of 3 to sit around for hours waiting on the inspector to arrive. Personally, I'd see if they'd take half when done, and the rest contingent on it passing inspection. You'd have to really mess up to make this fail an inspection. WHen I had mine done, I paid the guy, and the inspector came out maybe the next day, but there wasn't as much money at stake. At Home Depot (not where the installers probably would buy their wire), 8g is $0.59/foot, 10g is cheaper. EMT is cheap. A 40A breaker should come in at less than $40. Throw in some hangers and fittings, materials costs aren't really all that much. Screwing the thing to the wall is nothing...at least some of them come with bolts, and if they don't, that's less than $5 easily.
Now, there could be issues that we can't see, but I would be surprised if someone local can't do this and for a lot less money. Three wires at each end, and once the wire is run, maybe an hour to finish up mounting and connecting everything. A master electrican and, if he needs a helper (mine didn't) is probably in the order of $150/hour, maybe $500 in materials, and give them maybe 3-hours. That's a wag without being there and seeing exactly what's needed. THe EVSE would be extra (I bought mine rather than having it supplied).