It seems they are getting off easy and the city is selling out. Frankly, planting trees as part of a city road project is the city's responsibility. I would begin by making them acquire and preserve a similar tree stand elsewhere in the city (if possible). Secondly, there should be a guaranteed minimum size on the replacement trees on the hillside - 4" caliper, at least. They should also be of the same type as what was removed. Don't go repacing quercus macrocarpa or carya ovata with acer platinoides or (eek!) acer negundo. Recognizing that the environment of a mature savanna or woodland is far different than that of these new, much smaller trees, some additional environmental mitigation should be required. In addition to all of this mitigation, there should be a fine for every tree cut down.
Needless to say, the company should fire the dumb-ass responsible for this. If it was a franchise operator, they should loose their franchse.
My brother is the Parks & Planning Director in Highland Park, Illinois, a rich suburb on Chicago's north shore. Periodically, they have had some near lakeshore property owners go onto city land(!) to cut down mature hardwoods that block their view of the lake. Of course, they also have the problem of people tearing down beautiful Victorian mansions to build big uglys.