Sachverhalt: A. Am 14. Oktober 2008 stellte die Swisscom (Schweiz) AG ein Gesuch um Errichtung einer Mobilfunk-Basisstation auf dem Dach des Gebäudes auf Parzelle Nr. 6717 an der Tittwiesenstrasse 29 in Chur. Mit Entscheid vom 11. Januar 2010 wies der Stadtrat Chur die dagegen erhobenen Einsprachen ab, soweit er darauf eintrat, und erteilte die Baubewilligung unter Auflagen und Bedingungen. Ein Teil der Einsprecher (darunter die im Rubrum aufgeführten Beschwerdeführer) erhoben gegen diesen Entscheid Beschwerde beim Verwaltungsgericht des Kantons Graubünden. Sie machten insbesondere geltend, ihr Anspruch auf rechtliches Gehör sei verletzt worden, weil ihnen ein Schreiben vom 10. Dezember 2009 der Swisscom (Schweiz) AG an die Stadt Chur betreffend die Standortevaluation und das Mobilfunkkonzept für das Jahr 2010 vorenthalten worden sei. Mit Urteil vom 7. September 2010 wies das Verwaltungsgericht die Beschwerde ab. Es erwog, die geltend gemachte Gehörsverletzung sei im Rahmen des Schriftenwechsels vor Verwaltungsgericht geheilt worden. Die übrigen Rügen, insbesondere bezüglich angeblicher weiterer Gehörsverletzungen, hielt es für unbegründet. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 1. Februar 2011 beantragen die im Rubrum genannten Beschwerdeführer, das Urteil des Verwaltungsgerichts sei aufzuheben und die Angelegenheit sei zur neuen Beurteilung an die Vorinstanz zurückzuweisen. Das Verwaltungsgericht und die Stadt Chur beantragen in ihrer jeweiligen Vernehmlassung die Abweisung der Beschwerde, soweit darauf eingetreten werde. Die Beschwerdegegnerin schliesst auf Abweisung der Beschwerde. Das ebenfalls zur Vernehmlassung eingeladene Amt für Natur und Umwelt des Kantons Graubünden hat sich nicht vernehmen lassen. In ihrer Stellungnahme dazu halten die Beschwerdeführer im Wesentlichen an ihren Anträgen und Rechtsauffassungen fest. Mit Präsidialverfügung vom 28. Februar 2011 hat das Bundesgericht der Beschwerde die aufschiebende Wirkung zuerkannt. 