300 DPI gives superb quality that you can look at very close distances. Obviously an image that’s two meters wide is looked at couple of meters away and then 100DPI is quite enough. I have printed images with 90 DPI with Epson SP 9900, which is 44 inch fine art printer and they were still quite ok. I would go with 180 DPI with Epson or 200 DPI with Canon fine art printer. They will still produce gallery-quality prints. Then again my experience is mostly from photographs and digitally created images may behave differently.
Then again print shop should know what they are doing. I would look for another print shop that is not stuck with overly high image quality requirements.