Sachverhalt: A. Am 19. September 2014 wurde ein erstes Baugesuch der F._ AG für die Erstellung eines Garni/Pensionshauses auf Parzelle 3690 in der Dorferweiterungszone (DE3) der Gemeinde Breil/Brigels publiziert. Dagegen wurde Einsprache erhoben und das Baugesuch wurde am 11. Februar 2015 vom Gemeindevorstand abgeschrieben. B. Bereits am 15. Dezember 2014 hatte die F._ AG ein weiteres, ähnliches Baugesuch um Erstellung eines Garni/Pensionshauses auf Parzelle 3690 eingereicht. Die Gebäudehöhe beträgt laut Angaben im Baugesuch 8.68 m und die Firsthöhen 12.85 m/11.29 m (zulässig sind gemäss Zonenschema in der DE3 maximal 10 m Gebäudehöhe und 13 m Firsthöhe). Total soll die Baute 14 Zimmer und 30 Gästebetten aufweisen. Gegen das Baugesuch erhoben die Eheleute A. und B. A._ (Eigentümer Parzelle 565) und einzelne Stockwerkeigentümer auf den benachbarten Grundstücken Parzelle 4148 (Casa Inis) und Parzelle 3687 (Casa Selina) am 7. Januar 2015 Einsprache und beantragten die Abweisung des Baugesuchs. Die Gemeinde beauftragte die Geometerin Madeleine Grob, den massgebenden Terrainverlauf zu ermitteln und Gebäude- und Firsthöhen zu überprüfen. Diese kam zum Ergebnis, das Bauprojekt halte die vorgeschriebenen Gebäude- und Firsthöhen im Rahmen der möglichen Ermittlungs- und Kontrollgenauigkeit ein. Am 23. März wies der Gemeindevorstand die Einsprache ab und erteilte gleichentags dem Bauvorhaben die Bewilligung. C. Dagegen erhoben die Einsprecher am 23. April 2015 Beschwerde an das Verwaltungsgericht des Kantons Graubünden. Dieses wies die Beschwerde am 28. Oktober 2015 ab, soweit es darauf eintrat. D. Gegen den am 18. Dezember 2015 zugestellten Entscheid haben A. und B. A._ und die übrigen im Rubrum genannten Einsprecher am 1. Februar 2016 Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht erhoben. Sie beantragen, der angefochtene Entscheid sei aufzuheben und die Erteilung der Baubewilligung sei zu verweigern. Eventualiter sei die Angelegenheit im Sinne der Erwägungen zur Neubeurteilung an die Vorinstanz zurückzuweisen. E. Die Gemeinde Breil/Brigels und das Verwaltungsgericht beantragen, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Die F._ AG hat auf eine Vernehmlassung verzichtet. Das BAFU kommt in seiner Vernehmlassung zum Ergebnis, der angefochtene Entscheid sei mit Bundesumweltrecht konform. Im weiteren Schriftenwechsel halten die Beteiligten an ihren Anträgen fest. F. Mit Verfügung vom 2. März 2016 wurde der Beschwerde die aufschiebende Wirkung zuerkannt.