Sachverhalt: A. Mit Eingabe vom 29. Juni 2005 stellte die TDC Switzerland AG (seit 28. September 2007: Sunrise Communications AG) ein Baugesuch für die Erstellung einer Mobilfunkantenne (Basisstation GSM 1800 und UMTS). Das Baugesuch sieht vor, die rund 8 m hohe Antenne auf dem Dach des Gebäudes auf Parzelle Nr. 88 (neu: Parzelle Nr. 5088) an der Romanshornerstrasse 5 in Kreuzlingen zu errichten. Am 27. Mai 2008 erteilte der Stadtrat von Kreuzlingen die Baubewilligung und wies die Einsprachen von 448 Personen ab, soweit er darauf überhaupt eintrat. Dagegen erhoben 112 Personen Rekurs beim Departement für Bau und Umwelt des Kantons Thurgau. Mit Entscheid vom 24. Februar 2009 wies das Departement die Rekurse ab, soweit es darauf eintrat. Ein gegen diesen Entscheid erhobene Beschwerde wurde vom Verwaltungsgericht des Kantons Thurgau mit Urteil vom 23. September 2009 ebenfalls abgewiesen. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 2. November 2009 verlangen die im Rubrum genannten Personen, die Entscheide des Verwaltungsgerichts, des Departements für Bau und Umwelt sowie der politischen Gemeinde Kreuzlingen seien aufzuheben und die Baubewilligung sei zu verweigern. Eventualiter sei die Angelegenheit zur neuen Beurteilung an die Vorinstanz zurückzuweisen. Das Verwaltungsgericht und die Beschwerdegegnerin beantragen in ihrer jeweiligen Vernehmlassung, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Das Departement für Bau und Umwelt schliesst auf Abweisung der Beschwerde. Der Stadtrat von Kreuzlingen hat auf eine Stellungnahme verzichtet. Das ebenfalls zur Vernehmlassung eingeladene Bundesamt für Umwelt (BAFU) kommt zum Schluss, die Bestimmungen der Verordnung vom 23. Dezember 1999 über den Schutz vor nichtionisierender Strahlung (NISV; SR 814.710) seien eingehalten, sofern die Orte mit empfindlicher Nutzung (OMEN) des Gebäudes an der Kamorstrasse 2 richtig lokalisiert worden seien. In ihrer Stellungnahme dazu halten die Beschwerdeführer im Wesentlichen an ihren Anträgen und Rechtsauffassungen fest. Mit Schreiben vom 15. April 2010 reichte die Beschwerdegegnerin unaufgefordert eine weitere Stellungnahme ein. Schliesslich holte das Bundesgericht vom Bundesamt für Kommunikation (BAKOM) und vom BAFU eine Stellungnahme zu einzelnen konkreten Fragen ein. Diese Stellungnahmen wurden den übrigen Verfahrensbeteiligten zur Kenntnis gebracht.