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.

Erwägungen:
1. 1.1 Beim angefochtenen Urteil handelt es sich um einen kantonal letztinstanzlichen Entscheid über die Baubewilligung für eine Mobilfunkanlage, welcher der Beschwerde in öffentlich-rechtlichen Angelegenheiten unterliegt (<ref-law>). Gemäss jenem Entscheid des Verwaltungsgerichts wohnt zumindest ein Teil der Beschwerdeführer innerhalb des Perimeters, in dem die Strahlung noch 10 % des Anlagegrenzwerts beträgt. Die betreffenden Personen sind damit gemäss der bundesgerichtlichen Rechtsprechung grundsätzlich zur Beschwerde legitimiert (Art. 89 Abs. 1 lit. b und c BGG; <ref-ruling> E. 2 S. 169 ff. mit Hinweisen). Ob das Beschwerderecht sämtlichen Beschwerdeführern zukommt, kann offen gelassen werden. Auf die Beschwerde ist deshalb unter Vorbehalt der nachfolgenden Erwägungen einzutreten.
1.2 Unzulässig ist der Antrag der Beschwerdeführer, auch den Entscheid des Departements für Bau und Umwelt vom 24. Februar 2009 sowie den Entscheid des Stadtrats von Kreuzlingen vom 27. Mai 2008 aufzuheben. Diese sind durch das Urteil des Verwaltungsgerichts ersetzt worden (Devolutiveffekt) und gelten als inhaltlich mitangefochten (<ref-ruling> E. 1.4 S. 144 mit Hinweis).
1.2 Unzulässig ist der Antrag der Beschwerdeführer, auch den Entscheid des Departements für Bau und Umwelt vom 24. Februar 2009 sowie den Entscheid des Stadtrats von Kreuzlingen vom 27. Mai 2008 aufzuheben. Diese sind durch das Urteil des Verwaltungsgerichts ersetzt worden (Devolutiveffekt) und gelten als inhaltlich mitangefochten (<ref-ruling> E. 1.4 S. 144 mit Hinweis).
1.3 1.3.1 Nach <ref-law> ist in der Begründung in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Dies setzt voraus, dass sich der Beschwerdeführer wenigstens kurz mit den Erwägungen des angefochtenen Entscheids auseinandersetzt. Zwar wendet das Bundesgericht das Recht grundsätzlich von Amtes wegen an (<ref-law>). Das setzt aber voraus, dass auf die Beschwerde überhaupt eingetreten werden kann, diese also wenigstens die Begründungsanforderungen von <ref-law> erfüllt.
Strengere Anforderungen gelten, wenn die Verletzung von Grundrechten (einschliesslich der willkürlichen Anwendung von kantonalem Recht und Willkür bei der Sachverhaltsfeststellung) geltend gemacht wird. Dies prüft das Bundesgericht nicht von Amtes wegen, sondern nur insoweit, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>). Die Beschwerdeschrift muss die wesentlichen Tatsachen und eine kurz gefasste Darlegung darüber enthalten, welche verfassungsmässigen Rechte bzw. welche Rechtssätze inwiefern durch den angefochtenen Erlass oder Entscheid verletzt worden sind. Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen. Wird eine Verletzung des Willkürverbots geltend gemacht, muss anhand der angefochtenen Subsumtion im Einzelnen dargelegt werden, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 1.6 S. 130; <ref-ruling> E. 2.1 und 2.2 S. 245 f.; je mit Hinweisen).
1.3.2 Die Beschwerdeführer bringen vor, im Standortdatenblatt seien nicht die drei am stärksten belasteten OMEN ausgewiesen worden. Auch das Amt für Umwelt habe dies schliesslich bestätigen müssen. Dazu führte das Verwaltungsgericht aus, dass das Amt für Umwelt die Berechnung nachträglich korrigiert habe. Entscheidend sei indessen, dass selbst der von den Beschwerdeführern ermittelte Wert unter dem Anlagegrenzwert liege. Auf diese Erwägung im vorinstanzlichen Entscheid gehen die Beschwerdeführer nicht ein. Ihre Rüge erweist sich deshalb als nicht hinreichend substanziiert, sodass darauf nicht einzutreten ist.
1.3.3 Die Beschwerdeführer beantragen, die Baugesuchstellerin habe gemeinsam mit anderen Mobilfunknetzbetreiberinnen im betroffenen Quartier für eine Standortkoordination zu sorgen. Sie verweisen auf eine vom Bundesamt für Kommunikation (BAKOM) veröffentlichte UMTS-Musterkonzession, die inhaltlich vermutlich der Konzession der Baugesuchstellerin entspreche. Zudem argumentieren sie, dass das Fernmeldegesetz vom 30. April 1997 (FMG; SR 784.10) einer Koordination nicht entgegenstehe und dass eine vom Gemeindeparlament von Kreuzlingen erheblich erklärte Motion ebenfalls eine Koordinationspflicht vorsehe.
Mit dieser Argumentation zeigen die Beschwerdeführer nicht auf, inwiefern der angefochtene Entscheid im Sinne von <ref-law> Recht verletzt. Die Vorinstanz hat denn auch dargelegt, dass keine gesetzliche Grundlage bestehe, um wegen fehlender Koordination die Baubewilligung zu verweigern. Die Beschwerde erweist sich damit auch in dieser Hinsicht als nicht hinreichend begründet, weshalb auf das Vorbringen nicht einzutreten ist. Im Übrigen ist darauf hinzuweisen, das sich die von den Beschwerdeführern angerufene Klausel der UMTS-Musterkonzession auf <ref-law> bezieht und in diesem Zusammenhang auszulegen ist. Gemäss <ref-law> kann das Bundesamt für Kommunikation auf Antrag aus Gründen des öffentlichen Interesses, namentlich um den Anliegen der Raumplanung, des Landschafts-, Heimat-, Umwelt-, Natur- und Tierschutzes oder technischen Schwierigkeiten Rechnung zu tragen, Anbieterinnen von Fernmeldediensten verpflichten, Dritten gegen angemessenes Entgelt die Mitbenutzung ihrer Fernmeldeanlagen und anderer Anlagen, wie Kabelkanäle und Sendestandorte, zu gestatten, wenn die Anlagen über ausreichende Kapazität verfügen. Die Lektüre der Norm in ihrem Kontext erhellt, dass es um ein Zweiparteienverfahren geht (vgl. Urteile 1P.562/2001 vom 13. Juni 2002 E. 6, in: RDAT 2002 II Nr. 56 S. 195; 2A.503/2000 vom 3. Oktober 2001 E. 10, in: ZBl 103/2002 S. 244; je mit Hinweisen). Zudem wird ausdrücklich erwähnt, dass das Bundesamt nur auf Antrag tätig werden kann (vgl. dazu Botschaft vom 12. November 2003 zur Änderung des Fernmeldegesetzes, BBl 2003 7984 Ziff. 2.1.5). Eine Grundlage, um im Sinne der Argumentation der Beschwerdeführer die Baugesuchstellerin zur Standortkoordination zu verpflichten, stellt <ref-law> nicht dar.
Mit dieser Argumentation zeigen die Beschwerdeführer nicht auf, inwiefern der angefochtene Entscheid im Sinne von <ref-law> Recht verletzt. Die Vorinstanz hat denn auch dargelegt, dass keine gesetzliche Grundlage bestehe, um wegen fehlender Koordination die Baubewilligung zu verweigern. Die Beschwerde erweist sich damit auch in dieser Hinsicht als nicht hinreichend begründet, weshalb auf das Vorbringen nicht einzutreten ist. Im Übrigen ist darauf hinzuweisen, das sich die von den Beschwerdeführern angerufene Klausel der UMTS-Musterkonzession auf <ref-law> bezieht und in diesem Zusammenhang auszulegen ist. Gemäss <ref-law> kann das Bundesamt für Kommunikation auf Antrag aus Gründen des öffentlichen Interesses, namentlich um den Anliegen der Raumplanung, des Landschafts-, Heimat-, Umwelt-, Natur- und Tierschutzes oder technischen Schwierigkeiten Rechnung zu tragen, Anbieterinnen von Fernmeldediensten verpflichten, Dritten gegen angemessenes Entgelt die Mitbenutzung ihrer Fernmeldeanlagen und anderer Anlagen, wie Kabelkanäle und Sendestandorte, zu gestatten, wenn die Anlagen über ausreichende Kapazität verfügen. Die Lektüre der Norm in ihrem Kontext erhellt, dass es um ein Zweiparteienverfahren geht (vgl. Urteile 1P.562/2001 vom 13. Juni 2002 E. 6, in: RDAT 2002 II Nr. 56 S. 195; 2A.503/2000 vom 3. Oktober 2001 E. 10, in: ZBl 103/2002 S. 244; je mit Hinweisen). Zudem wird ausdrücklich erwähnt, dass das Bundesamt nur auf Antrag tätig werden kann (vgl. dazu Botschaft vom 12. November 2003 zur Änderung des Fernmeldegesetzes, BBl 2003 7984 Ziff. 2.1.5). Eine Grundlage, um im Sinne der Argumentation der Beschwerdeführer die Baugesuchstellerin zur Standortkoordination zu verpflichten, stellt <ref-law> nicht dar.
1.4 1.4.1 Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als der Entscheid der Vorinstanz dazu Anlass gibt, was in der Beschwerde näher darzulegen ist (<ref-law>; <ref-ruling> E. 2.2.1 S. 226 mit Hinweis).
1.4.2 Die Beschwerdeführer rügen eine willkürliche Feststellung des Sachverhalts. Sie machen geltend, gemäss ihren Prognoseberechnungen werde im Gebäude an der Kamorstrasse 2 der Anlagegrenzwert überschritten. Weiter weisen sie darauf hin, dass an der Romanshornerstrasse 2 und der Besmerstrasse 1 elektrotechnische Unternehmen industrielle Steuerungs- und Schaltanlagen entwickeln und produzieren würden. Durch die Mobilfunkantenne könnten erhebliche Sach- und Personenschäden entstehen.
Diese Tatsachen haben die Beschwerdeführer im vorinstanzlichen Verfahren nicht geltend gemacht. Im angefochtenen Entscheid finden sich denn auch keine entsprechenden Ausführungen. Da die Beschwerdeführer nicht aufzeigen, inwiefern erst der Entscheid der Vorinstanz zu diesen neuen Vorbringen Anlass gegeben hat, ist darauf nicht einzutreten.
1.4.3 Aus demselben Grund ist auf die Rüge, der Augenschein des kantonalen Amts für Denkmalpflege habe ohne die Beschwerdeführer stattgefunden, nicht einzutreten. Auch dieses Vorbringen, mit dem eine Verweigerung des rechtlichen Gehörs nachgewiesen werden soll, ist neu und gemäss <ref-law> unzulässig.
1.5 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Soweit ein Beschwerdeführer die vorinstanzlichen Sachverhaltsfeststellungen beanstandet und eine mangelhafte Sachverhaltsfeststellung für den Ausgang des Verfahrens entscheidend ist, kann er nur geltend machen, die Feststellungen seien offensichtlich unrichtig oder beruhten auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 97 Abs. 1 und <ref-law>). Eine entsprechende Rüge ist substanziiert vorzubringen (<ref-law>). Vorbehalten bleibt die Sachverhaltsberichtigung von Amtes wegen nach <ref-law> (<ref-ruling> E. 1.5 S. 129 f.; <ref-ruling> E. 1.4.3 S. 254 f.; Urteil des Bundesgerichts 1C_412/2008 vom 24. März 2009 E. 2.1; je mit Hinweisen).
Die Beschwerdeführer stellen einleitend in ihrer Eingabe an das Bundesgericht den Sachverhalt aus eigener Sicht dar, ohne ihre Ausführungen mit einer Rüge am Entscheid der Vorinstanz zu verbinden. Es besteht nach dem Gesagten insofern kein Anlass, von den Sachverhaltsfeststellungen im angefochtenen Entscheid abzuweichen.
2. 2.1 Nach Ansicht der Beschwerdeführer liegen genügend wissenschaftliche Studien vor, die nachweisen, dass die Grenzwerte der NISV zu hoch angesetzt sind. Sie kritisieren, das BAFU sei bei der Evaluation wissenschaftlicher Studien zu streng, und berufen sich auf das Vorsorgeprinzip (<ref-law>; Art. 1 Abs. 2 und <ref-law> [SR 814.01]).
2. 2.1 Nach Ansicht der Beschwerdeführer liegen genügend wissenschaftliche Studien vor, die nachweisen, dass die Grenzwerte der NISV zu hoch angesetzt sind. Sie kritisieren, das BAFU sei bei der Evaluation wissenschaftlicher Studien zu streng, und berufen sich auf das Vorsorgeprinzip (<ref-law>; Art. 1 Abs. 2 und <ref-law> [SR 814.01]).
2.2 2.2.1 Die Anlage- und Immissionsgrenzwerte der NISV hat das Bundesgericht bisher stets als gesetzes- und verfassungskonform beurteilt (Urteile 1C_45/2009 vom 6. Juli 2009 E. 3.2; 1C_282/2008 vom 7. April 2009 E. 4; 1C_92/2008 vom 16. Dezember 2008 E. 3.3-3.6; 1C_316/2007 vom 30. April 2008 E. 5.1; 1C_170/2007 vom 20. Februar 2008 E. 2; je mit Hinweisen). Auch neuere Forschungen haben danach keine wissenschaftlich genügenden Studien hervorgebracht, welche einen hinreichenden Zusammenhang zwischen der Exposition durch Mobilfunkbasisstationen und schädlichen oder lästigen Einwirkungen herstellen (vgl. BAFU [Hrsg.], Hochfrequente Strahlung und Gesundheit: Bewertung von wissenschaftlichen Studien im Niedrigdosisbereich, 2. Aufl. 2007, S. 10 ff., 72 f., 98 ff., 105 f. und 131; «http://www.bafu.admin.ch/publikationen» [besucht am 13. Juli 2010]). Die wissenschaftliche Datenlage für die Beurteilung der Gesundheitsgefährdung der Bevölkerung durch hochfrequente Strahlung im Niedrigdosisbereich, namentlich durch Mobilfunkbasisstationen, ist jedoch noch immer sehr lückenhaft. Forschung auf diesem Gebiet ist deshalb wichtig (Urteil 1C_45/2009 vom 6. Juli 2009 E. 3.2 mit Hinweis).
2.2.2 Es ist in erster Linie Sache der zuständigen Fachbehörden (und nicht des Bundesgerichts), die internationale Forschung sowie die technische Entwicklung zu verfolgen und gegebenenfalls eine Anpassung der Grenzwerte der NISV zu beantragen (Urteil 1C_45/2009 vom 6. Juli 2009 E. 3.2 mit Hinweis). Das BAFU ist bisher dieser Aufgabe nachgekommen, indem es unter anderem in seinem Bericht "Hochfrequente Strahlung und Gesundheit" einschlägige wissenschaftliche Studien analysierte und bewertete. Die erste Auflage dieses Berichts erschien im Jahr 2003, die zweite, aktualisierte Auflage im Jahr 2007 (vgl. die oben erwähnte Internet-Fundstelle). Ein ständiges Monitoring der neuen wissenschaftlichen Literatur erfolgt zudem in der Dokumentationsstelle ELMAR, welche im Auftrag des BAFU geführt wird («http://www.elmar.unibas.ch/index.html» [besucht am 13. Juli 2010]).
2.2.3 Das Argument der Beschwerdeführer, das BAFU sei bei der Bewertung der Studien viel zu streng und das Vorsorgeprinzip verlange, auch vorläufige wissenschaftliche Befunde zu berücksichtigen, ist vor dem Hintergrund der Konzeption der Umweltschutzgesetzgebung nicht stichhaltig. Deren Immissionsgrenzwerte beruhen von ihrer Anlage her auf wissenschaftlich erhärteten Erkenntnissen und lassen deshalb keinen Raum für die Berücksichtigung von Studien, welche wissenschaftlichen Massstäben nicht zu genügen vermögen oder auf ihre Zuverlässigkeit bisher nicht überprüft worden sind (in diesem Sinne bereits <ref-ruling> E. 3b S. 402 f.; SCHRADE/LORETAN, in: Kommentar zum Umweltschutzgesetz, 2. Aufl. 2002, N. 9 zu <ref-law>, vgl. auch N. 38 zu <ref-law>). Das BAFU stellt diesbezüglich darauf ab, ob eine Studie ein Peer-Review-Verfahren durchlaufen hat (ein Verfahren zur Beurteilung der Qualität von wissenschaftlichen Arbeiten durch unabhängige Gutachter vor der Publikation mit dem Ziel der Qualitätssicherung der wissenschaftlichen Berichterstattung) und ob eine unabhängige Wiederholung das Ergebnis bestätigt. Ein Effekt wird demnach als gesichert erachtet, wenn er einer streng wissenschaftlichen Beweisführung standhält, das heisst mehrfach unabhängig repliziert worden ist, ein plausibles Wirkungsmodell existiert und er nicht im Widerspruch zu anderen Forschungsergebnissen steht (BAFU, a.a.O., S. 47).
Was die Anlagegrenzwerte anbelangt, basiert deren spezifische Festlegung nicht auf den Kriterien der Schädlichkeit oder Belästigung; sie richten sich vielmehr nach den technischen, betrieblichen und wirtschaftlichen Möglichkeiten (<ref-law>; <ref-ruling> E. 3.1 S. 175 mit Hinweisen). Zwar trifft zu, dass der Anlagegrenzwert als Konkretisierung des Vorsorgeprinzips das Risiko schädlicher Wirkungen, die zum Teil erst vermutet werden und noch nicht absehbar sind, möglichst gering halten soll (<ref-ruling> E. 3b S. 403 mit Hinweis). Und in diesem Sinne ist auch richtig, dass der Anlagegrenzwert eine Art Sicherheitsmarge schafft, indem auf wissenschaftliche Gewissheit verzichtet wird (ALAIN GRIFFEL, Die Grundprinzipien des schweizerischen Umweltrechts, 2001, S. 60 f.). Daraus folgt jedoch keineswegs, dass lediglich vorläufige wissenschaftliche oder erfahrungsbasierte Befunde den Massstab für die Bestimmung der konkreten Höhe des Anlagegrenzwerts abgeben. In seiner Vernehmlassung weist das BAFU in diesem Zusammenhang auch darauf hin, dass gegen eine rasche und unkritische Integration von nicht gefestigten Ergebnissen in ein Schutzkonzept gerade im Bereich der nichtionisierenden Strahlung die Tatsache spreche, dass in den vergangenen 20 Jahren unerklärliche Einzelbefunde in Nachfolgeuntersuchungen zum Teil nicht repliziert werden konnten. Ein Abstellen auf derartige vorläufige Erkenntnisse hätte vor diesem Hintergrund auch eine beträchtliche Rechtsunsicherheit zur Folge.
In Bezug auf die erwähnte Sicherheitsmarge zwischen dem (höheren) Immissionsgrenzwert und dem (tieferen) Anlagegrenzwert ist zu ergänzen, dass jede Mobilfunkanlage an OMEN den Anlagegrenzwert ausschöpfen darf (Art. 3 Abs. 3 und 6 NISV; Ziff. 64 und 65 Anhang 1 NISV). Dies bedeutet zwar, dass es im Einzelfall zu einer Kumulation der Strahlung von zwei oder mehreren Anlagen in Bezug auf einen OMEN kommen kann und dadurch die elektrische Feldstärke dort über den Anlagegrenzwert ansteigt. Einer derartigen Kumulation sind jedoch dadurch Grenzen gesetzt, dass nach Ziff. 62 Anhang 1 NISV Antennengruppen, die aus einem engen räumlichen Zusammenhang senden, als eine Anlage gelten. Zudem weist das BAFU darauf hin, dass sich die Feldstärken nicht einfach addieren, wenn ein bestimmter OMEN von mehreren als eigenständig zu qualifizierenden Anlagen bestrahlt wird. Würden zwei Anlagen in Bezug auf einen OMEN den ihnen zustehenden Anlagegrenzwert ausschöpfen, so resultierte eine kumulierte elektrische Feldstärke von 141 % des Anlagegrenzwerts; bei drei Anlagen wären es maximal 173 %. Der Immissionsgrenzwert würde schliesslich erst in der praktisch nicht möglichen Situation erreicht, wenn 100 Mobilfunkanlagen den betreffenden OMEN in der Höhe des Anlagegrenzwerts bestrahlen würden.
2.2.4 Konkret zitieren die Beschwerdeführer verschiedene Studien und Berichte und weisen auf Entwicklungen im In- und Ausland hin. Unter anderem verweisen sie auf die gesetzgeberische Entwicklung in Belgien. Hierzu legt das BAFU dar, soweit ersichtlich stelle einzig die Verordnung der Region Brüssel (Ordonnance relative à la protection de l'environnement contre les éventuels effets nocifs et nuisances provoqués par les radiations non ionisantes) vom 1. März 2007 strengere Anforderungen an die Begrenzung der Strahlung von Mobilfunkanlagen als die schweizerische NISV. Diese belgische Verordnung werde jedoch offenbar noch nicht angewendet, was auf ein Rechtsmittelverfahren und die Ausarbeitung von Ausführungsbestimmungen zurückzuführen sei. Entsprechend bestünden keine Erfahrungen in der Praxis und könnten derzeit für die Schweiz auch keine Schlüsse gezogen werden.
Insgesamt vermögen die Beschwerdeführer nicht aufzuzeigen, dass die zuständigen Fachbehörden oder der Bundesrat als Verordnungsgeber angesichts einer wissenschaftlich nachgewiesenen Gefährdung oder Belästigung untätig geblieben sind und es unterlassen haben, eine gebotene Anpassung der Grenzwerte zu beantragen beziehungsweise vorzunehmen. Nach dem Gesagten rechtfertigen es auch die bestehenden Wissenslücken nicht, die Grenzwerte der NISV als rechtswidrig zu beurteilen und den weiteren Bau von Mobilfunkantennen zu verbieten (vgl. Urteil 1C_45/2009 vom 6. Juli 2009 E. 3.2 mit Hinweis). Die kantonalen Behörden haben damit zu Recht die geltenden Immissions- und Anlagegrenzwerte der NISV angewandt. Die Rüge der Beschwerdeführer erweist sich als unbegründet.
3. 3.1 Die Beschwerdeführer kritisieren weiter, dass es noch keine verbindliche Norm zur Messung von UMTS-Strahlung gebe. Das Bundesgericht habe die zuständigen Behörden zu einer sofortigen Festlegung quantitativer Messtoleranzen zu verpflichten.
3.2 Das Bundesgericht hat in seiner bisherigen Rechtsprechung die bestehenden Messverfahren und -geräte sowie den Entwurf einer Messempfehlung für UMTS-Strahlung des Bundesamts für Umwelt, Wald und Landschaft (BUWAL, heute: BAFU) und des Bundesamts für Metrologie (METAS) vom 17. September 2003 genügen lassen (Urteile 1C_316/2007 vom 30. April 2008 E. 9; 1A.129/2006 vom 10. Januar 2007 E. 4, nicht publ. in: <ref-ruling>; 1A.57/2006 vom 6. September 2006 E. 6, in: ZBl 108/2007 S. 453; je mit Hinweisen). Gemäss einer Medienmitteilung des Eidgenössischen Departements für Umwelt, Verkehr, Energie und Kommunikation (UVEK) vom 23. Januar 2007 haben vom METAS organisierte Vergleichsmessungen ergeben, dass die Signale von UMTS-Antennen zuverlässig gemessen werden können. Die Resultate würden den erwähnten Entwurf der Messempfehlung für UMTS-Strahlung des BUWAL und des METAS bestätigen. Es habe sich gezeigt, dass die Streuung der Resultate von code-selektiven UMTS-Messungen mit jener der Messung von GSM-Signalen vergleichbar sei («http://www.uvek.admin.ch/dokumentation/ 00474/00492/index.html?lang=de&msg-id=10310» und «http://www. metas.ch/2006-218-598» [besucht am 13. Juli 2010]). Der Antrag der Beschwerdeführer ist deshalb abzuweisen.
4. 4.1 Die Beschwerdeführer rügen, das Qualitätssicherungssystem der Beschwerdegegnerin sei ungenügend. Es bestehe die Möglichkeit von Manipulationen. Zudem würden die gemessenen Daten nicht im Sinne einer Rückkoppelung automatisch auf die Systemsteuerung zurückwirken.
4.2 Die Qualitätssicherungssysteme dienen der Kontrolle, dass die bewilligten Parameter (äquivalente Strahlungsleistung ERP, Senderichtung) der Mobilfunkantennen im Betrieb eingehalten und die Grenzwerte der NISV nicht überschritten werden. Diese Kontrolle ist in <ref-law> vorgesehen. Die Verordnung schreibt jedoch nicht vor, auf welche Weise sie zu erfolgen hat. Das Bundesgericht hatte letztmals in seinem Urteil 1C_282/2008 vom 7. April 2009 Gelegenheit, zu den bestehenden Qualitätssicherungssystemen eingehend Stellung zu nehmen. Es wies auf die 2007 durchgeführte Überprüfung der Qualitätssicherungssysteme der Mobilfunknetzbetreiber Orange, Sunrise, Swisscom und Tele2 hin. Es räumte ein, die Systeme wiesen noch Mängel auf. Insgesamt kam es jedoch zum Schluss, dass diese aus umweltschutzrechtlicher Sicht nicht zu beanstanden seien (a.a.O., E. 3). Die Kritik der Beschwerdeführer gibt keinen Anlass, auf diese Rechtsprechung zurückzukommen. Die Rüge, das zur Anwendung kommende Qualitätssicherungssystem sei ungenügend, ist demnach abzuweisen.
5. 5.1 Die Beschwerdeführer bringen vor, die unter Denkmalschutz stehende Liegenschaft "Blaues Haus" werde durch den geplanten Antennenmast in ihrem Erscheinungsbild empfindlich beeinträchtigt. Der Mast sei zusammen mit dem "Blauen Haus" nicht nur von der Romanshornerstrasse her, sondern auch aus Richtung der Egelseestrasse, des Blumenwegs und des Blauhaus-Kreisels gut sichtbar. Von der Anhöhe des Blumenwegs trete er sogar mit den ebenfalls geschützten Bauten der Seeburg in Erscheinung. Selbst wenn das Schutzobjekt "Blaues Haus" bereits durch andere Bauten in der Umgebung beeinträchtigt sei, dürfe gemäss Bundesgerichtspraxis dieser Zustand nicht noch weiter verschlechtert werden. Auch die Interessenabwägung der Vorinstanz bezüglich des angeblich überwiegenden öffentlichen Interesses an der konzessionskonformen Versorgung des Gemeindegebiets und der Sicherstellung eines funktionierenden Wettbewerbs gehe fehl. Schliesslich missachte der angefochtene Entscheid das Einordnungsgebot gemäss Art. 39 des Baureglements der Stadt Kreuzlingen vom 1. September 2000. Sinngemäss rügen die Beschwerdeführer eine willkürliche Anwendung dieser Bestimmung (<ref-law>).
In verfahrensrechtlicher Hinsicht machen die Beschwerdeführer in diesem Zusammenhang eine Verletzung des Anspruchs auf rechtliches Gehör geltend (<ref-law>). Das Verwaltungsgericht habe dem Antrag auf Durchführung eines Augenscheins nicht stattgegeben und sich zudem nicht hinreichend mit der vorgetragenen Kritik auseinandergesetzt.
5.2 Nach der ständigen Praxis des Bundesgerichts liegt Willkür in der Rechtsanwendung vor, wenn der angefochtene Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Das Bundesgericht hebt einen Entscheid jedoch nur auf, wenn nicht bloss die Begründung, sondern auch das Ergebnis unhaltbar ist. Dass eine andere Lösung ebenfalls als vertretbar oder gar zutreffender erscheint, genügt nicht (<ref-ruling> E. 3.1 S. 153; <ref-ruling> E. 3.1 S. 473 f.; je mit Hinweisen).
Die von den Beschwerdeführern angerufene Bestimmung des kommunalen Baureglements verlangt, dass Aussenantennen und Parabolspiegel, wo möglich, nicht sichtbar zu montieren sind; andernfalls haben sie sich bezüglich Farbe und Standort am Objekt und in der Umgebung zu integrieren. Es ist keineswegs willkürlich, wenn die Vorinstanz diese Bestimmung in Bezug auf eine Mobilfunkantenne, deren Errichtung in Erfüllung einer Bundesaufgabe erfolgt und die aus technischen Gründen die Gebäudedächer überragen muss, nicht als verletzt ansah (vgl. <ref-ruling> E. 2.2 S. 547 f. mit Hinweisen; Urteil 1A.6/2007 vom 6. September 2007 E. 4.3, in: URP 2008 S. 341). Die Rüge der Willkür erweist sich als unbegründet.
5.3 Auch die Rüge, die Vorinstanz habe das rechtliche Gehör verletzt, weil sie dem Antrag auf Durchführung eines Augenscheins nicht stattgegeben habe, erweist sich als unbegründet. In ihrer Beschwerde an das Verwaltungsgericht stellten die Beschwerdeführer den Antrag, "[es] sei ein Augenschein, zumindest in der Steuerzentrale der Sunrise Communications AG durchzuführen". Dass das Verwaltungsgericht davon ausging, dass im Zusammenhang mit den Fragen des Denkmalschutzes und des Ortsbildschutzes gar kein Augenschein beantragt wurde, wie es in seiner Vernehmlassung vom 10. November 2009 zu Handen des Bundesgerichts darlegt, ist angesichts des Wortlauts dieses Antrags nicht zu beanstanden. Im Übrigen hat das Verwaltungsgericht im angefochtenen Entscheid dargelegt, weshalb in der Steuerzentrale der Beschwerdegegnerin kein Augenschein durchgeführt werde. Die betreffenden Erwägungen beanstanden die Beschwerdeführer nicht.
5.4 Die Erteilung einer Baubewilligung für eine Mobilfunkanlage ist eine Bundesaufgabe im Sinne von Art. 2 des Bundesgesetzes vom 1. Juli 1966 über den Natur- und Heimatschutz (NHG; SR 451), weshalb die zuständigen Behörden zur Schonung der in <ref-law> genannten Schutzobjekte verpflichtet sind (<ref-ruling> E. 2.2 S. 547 f. mit Hinweisen). <ref-law> bestimmt, dass der Bund, seine Anstalten und Betriebe sowie die Kantone bei der Erfüllung von Bundesaufgaben dafür sorgen, dass das heimatliche Landschafts- und Ortsbild, geschichtliche Stätten sowie Natur- und Kulturdenkmäler geschont werden und, wo das allgemeine Interesse an ihnen überwiegt, ungeschmälert erhalten bleiben (Abs. 1). Sie erfüllen diese Pflicht unter anderem, indem sie Konzessionen und Bewilligungen nur unter Bedingungen oder Auflagen erteilen oder aber verweigern (Abs. 2 lit. b). Diese Pflicht gilt unabhängig von der Bedeutung des Objektes im Sinne von Artikel 4 NHG; eine Massnahme darf jedoch nicht weitergehen, als es der Schutz des Objektes und seiner Umgebung erfordert (Abs. 3).
5.5 Im angefochtenen Entscheid wird dargelegt, dass das Ortsbild von Kreuzlingen im Bundesinventar der schützenswerten Ortsbilder der Schweiz (ISOS) gemäss <ref-law> verzeichnet sei. Für die Baugruppe "Bebauung Romanshornerstrasse, Anfang 20. Jahrhundert" bestehe das Ziel indessen lediglich in der Erhaltung der Struktur. Demnach seien die Anordnung und Gestalt der Bauten und Freiräume zu bewahren und die für die Struktur wesentlichen Elemente und Merkmale integral zu erhalten. Dieses Erhaltungsziel werde durch das Bauprojekt offensichtlich nicht tangiert. Die Beschwerdeführer widersprechen dieser Einschätzung nicht. Zu Recht räumen sie zudem ein, dass Kreuzlingen mittlerweile aus dem ISOS entlassen worden ist (vgl. Anhang zur Verordnung vom 9. September 1981 über das Bundesinventar der schützenswerten Ortsbilder der Schweiz [VISOS; SR 451.12]).
In Bezug auf das "Blaue Haus" hielt das Verwaltungsgericht sodann fest, dass zwischen diesem und der geplanten Antenne kein direkter optischer Bezug bestehe. Die unmittelbare Umgebung des Hauses werde vielmehr durch die benachbarten Bauten geprägt. Diese Einschätzung ist nicht zu beanstanden. Sie bestätigt sich auch auf den von den Beschwerdeführern eingereichten Fotomontagen. Entgegen der Ansicht der Beschwerdeführer bedeutet der Umstand, dass aus gewissen Perspektiven sowohl das geschützte Objekt als auch die Antenne wahrgenommen werden können, nicht, dass ersteres durch letztere massgeblich beeinträchtigt würde. Dies gilt auch für eine weitere, von den Beschwerdeführern eingereichte Fotomontage, auf welcher im Vordergrund die Antenne und in der Ferne der See und der Seeburgpark zu erkennen sind.
Insofern kann nur von einer marginalen Beeinträchtigung des Ortsbilds und des unter Schutz gestellten "Blauen Hauses" gesprochen werden. Dem hat die Vorinstanz richtigerweise das Interesse an einer leistungsfähigen Mobilfunkversorgung gegenübergestellt. Im urbanen Gebiet besteht eine hohe Nachfrage für Mobilfunkdienste. Dies erfordert den Bau von Mobilfunkantennen, welche die Dächer überragen müssen, um ihre Funktion zu erfüllen. Insgesamt erweist sich die Interessenabwägung im vorinstanzlichen Entscheid, wonach im vorliegenden Fall das Interesse an der Mobilfunkversorgung stärker zu gewichten sei als der Ortsbild- und Denkmalschutz, nicht zu beanstanden (vgl. dazu etwa Urteil 1A.6/2007 vom 6. September 2007 E. 4.3, in: URP 2008 S. 341).
5.6 Die Vorinstanz hat nach dem Gesagten die wesentlichen Aspekte zum Heimatschutz und zur Denkmalpflege in ihre Erwägungen einbezogen und mit ihrer Interessenabwägung <ref-law> nicht verletzt. Ihr Entscheid genügt diesbezüglich auch den Begründungsanforderungen von <ref-law>. Diese Verfassungsgarantie verlangt nicht, dass sich die Behörde mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt. Vielmehr kann sie sich auf die für den Entscheid wesentlichen Punkte beschränken. Die Begründung muss so abgefasst sein, dass sich der Betroffene über die Tragweite des Entscheids Rechenschaft geben und ihn in voller Kenntnis der Sache an die höhere Instanz weiterziehen kann (<ref-ruling> E. 4.1 S. 88 mit Hinweisen). Diesen Anforderungen entspricht der angefochtene Entscheid. Die in ihm enthaltenen Ausführungen ermöglichten es den Beschwerdeführern, sich über dessen Tragweite Rechenschaft abzulegen und ihn sachgemäss anzufechten. Die Rüge der Verletzung von <ref-law> erweist sich damit als unbegründet.
6. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Diesem Ausgang des Verfahrens entsprechend sind die Gerichtskosten den unterliegenden Beschwerdeführern aufzuerlegen (<ref-law>). Sie haben der obsiegenden, anwaltlich vertretenen Beschwerdegegnerin eine dem Aufwand entsprechende Parteientschädigung zu bezahlen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2. Die Gerichtskosten von Fr. 4'000.-- werden den Beschwerdeführern auferlegt.
3. Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 1'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Politischen Gemeinde Kreuzlingen, dem Departement für Bau und Umwelt sowie dem Verwaltungsgericht des Kantons Thurgau, dem Bundesamt für Umwelt und dem Bundesamt für Kommunikation schriftlich mitgeteilt.
Lausanne, 20. Juli 2010
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Dold