Sachverhalt:
A. Mit Eingabe vom 28. Mai 2007 stellte die Orange Communications SA ein Baugesuch für die Erstellung einer Mobilfunkantenne (Basisstation UMTS). Das Baugesuch sieht vor, die rund 3.5 m hohe Antenne auf dem Dach des Gebäudes auf Parzelle Nr. 2047 an der Hauptstrasse 132 in Kreuzlingen zu errichten. Das Baugrundstück liegt in der Wohn- und Gewerbezone 90 (WG 90). Am 18. November 2008 erteilte die Politische Gemeinde Kreuzlingen die Baubewilligung und wies die Einsprachen von über 590 Personen ab, soweit sie überhaupt darauf eintrat. Dagegen erhoben 36 Personen Rekurs beim Departement für Bau und Umwelt des Kantons Thurgau. Nach Durchführung eines Augenscheins wies das Departement die Rekurse mit Entscheid vom 24. Juni 2009 ab, soweit es darauf eintrat. Eine gegen diesen Entscheid erhobene Beschwerde wurde vom Verwaltungsgericht des Kantons Thurgau mit Urteil vom 13. Januar 2010 ebenfalls abgewiesen, soweit darauf eingetreten wurde.
B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 22. Februar 2010 verlangen die im Rubrum genannten Personen im Wesentlichen, die Entscheide des Verwaltungsgerichts und der vorangehenden Instanzen seien aufzuheben und die Baubewilligung sei zu verweigern. Eventualiter sei die Angelegenheit zur Neubeurteilung an die Vorinstanzen zurückzuweisen und in diesem Zusammenhang auch eine Koordination aller im Quartier geplanten Mobilfunkanlagen vorzunehmen.
Während die Politische Gemeinde Kreuzlingen auf eine Vernehmlassung verzichtete, beantragen das Verwaltungsgericht und das Departement für Bau und Umwelt die Abweisung der Beschwerde. Die Orange Communications SA schliesst auf Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Das ebenfalls zur Vernehmlassung eingeladene Bundesamt für Umwelt (BAFU) kommt zum Schluss, die bundesrechtlichen Vorschriften über den Schutz vor nichtionisierender Strahlung seien im angefochtenen Entscheid korrekt angewendet worden. In ihrer Stellungnahme dazu ändern die Beschwerdeführer ihre Rechtsbegehren im Wesentlichen insofern, als dass sie neu nur noch die Aufhebung des Entscheids des Verwaltungsgerichts verlangen. Vom Antrag auf Aufhebung der Baubewilligung nehmen sie Abstand. Eventualiter beantragen sie neu zudem, die Bewilligung sei höchstens unter Auflagen zu erteilen.
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 (Art. 82 ff. BGG). Gemäss jenem Entscheid 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; BGE 128 II 168 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 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG). 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 Art. 95 BGG (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG). Eine entsprechende Rüge ist substanziiert vorzubringen (Art. 42 Abs. 2 BGG). Vorbehalten bleibt die Sachverhaltsberichtigung von Amtes wegen nach Art. 105 Abs. 2 BGG (BGE 135 III 127 E. 1.5 S. 129 f.; 133 II 249 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.
1.3 Nach Art. 42 Abs. 2 BGG 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 (Art. 106 Abs. 1 BGG). Das setzt aber voraus, dass auf die Beschwerde überhaupt eingetreten werden kann, diese also wenigstens die Begründungsanforderungen von Art. 42 Abs. 2 BGG 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 (Art. 106 Abs. 2 BGG). 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 (BGE 135 III 127 E. 1.6 S. 130; 134 II 244 E. 2.1 und 2.2 S. 245 f.; je mit Hinweisen).
1.4 Die Beschwerdeführer rügen, das Baugesuchsformular weise verschiedene Mängel auf und genüge keinesfalls allen gesetzlichen Anforderungen. Die Vorinstanz hält dazu fest, die Korrektur der Bezeichnung der Grundeigentümerschaft im Baugesuchsformular sei nicht von Relevanz. Unbestrittenermassen liege eine Vollmacht des Grundeigentümers zugunsten seines Bruders vor. Diesbezüglich sei kein Mangel zu erkennen. Zu Recht habe das Departement für Bau und Umwelt ausgeführt, dass es sich bei der Unterzeichnung des Baugesuchsformulars durch den Grundeigentümer nicht um ein "absolut zu erfüllendes Erfordernis" für die Gültigkeit des Baugesuchs handle, sondern vielmehr um eine Ordnungsvorschrift, welche offensichtlich sinnlose Baugesuche verhindern solle. Die Beschwerdeführer legen nicht dar, inwiefern der vorinstanzliche Entscheid in diesem Punkt gegen Recht verstösst (Art. 42 Abs. 2 BGG). Auf die Rüge ist nicht einzutreten.
1.5 Die Beschwerdeführer kritisieren, die Vorinstanz habe ihren Antrag auf Durchführung eines Augenscheins vor Ort abgewiesen. Damit sei ihr Anspruch auf rechtliches Gehör verletzt worden, zumal nicht nachvollziehbar sei, inwiefern die Mitglieder des Verwaltungsgerichts mit den örtlichen Verhältnissen hinreichend vertraut seien.
Entgegen der Darstellung der Beschwerdeführer berief sich das Verwaltungsgericht nicht ausschliesslich darauf, dass seine Mitglieder mit den örtlichen Verhältnissen vertraut seien. Es stellte vielmehr fest, dass sich die örtlichen Verhältnisse auch aus den in den Akten befindlichen, fotografischen Bilddokumentationen ergäben. Auf diesen Umstand gehen die Beschwerdeführer nicht ein. In der Tat enthalten die Akten verschiedene Fotos. Diese wurden zum einen offenbar anlässlich des Augenscheins durch das Departement für Bau und Umwelt erstellt, zum anderen von den Beschwerdeführern selbst eingereicht. Weshalb die Vorinstanz aufgrund dieser Beweismittel nicht willkürfrei davon ausgehen durfte, dass ein Augenschein ihre Überzeugung nicht zu ändern vermöchte, legen die Beschwerdeführer nicht hinreichend substanziiert dar (vgl. BGE 136 I 229 E. 5.3 S. 236 f. mit Hinweisen). Insoweit ist auf ihre Rüge der Verletzung des rechtlichen Gehörs nicht einzutreten (Art. 42 Abs. 2 i.V.m. Art. 106 Abs. 2 BGG).
1.6 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 Art. 95 BGG 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, dass sich die von den Beschwerdeführern angerufene Klausel der UMTS-Musterkonzession auf Art. 36 Abs. 2 FMG bezieht und in diesem Zusammenhang auszulegen ist. Gemäss Art. 36 Abs. 2 FMG 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. Zudem wird ausdrücklich erwähnt, dass das Bundesamt nur auf Antrag tätig werden kann. Eine Grundlage, um im Sinne der Argumentation der Beschwerdeführer die Baugesuchstellerin zur Standortkoordination zu verpflichten, stellt Art. 36 Abs. 2 FMG nicht dar (Urteil 1C_492/2009 vom 20. Juli 2010 E. 1.3.3 mit Hinweisen).
1.7 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 (Art. 99 Abs. 1 BGG; BGE 134 V 223 E. 2.2.1 S. 226 mit Hinweis). Die Beschwerdeführer rügen, an verschiedenen Orten mit empfindlicher Nutzung (OMEN) seien die Grenzwerte möglicherweise nicht eingehalten worden. Zudem seien im Gebäude auf Parzelle Nr. 361 elektrotechnische Unternehmen eingemietet, die industrielle Steuerungs- und Schaltanlagen entwickelten und produzierten. Die geplante Antenne könne erhebliche Sach- und Personenschäden zur Folge haben. Diese Vorbringen sind neu. Es ist weder ersichtlich noch wird von den Beschwerdeführern dargelegt, inwiefern erst der angefochtene Entscheid dazu Anlass gegeben hat. Die genannten Tatsachen sind deshalb nicht zulässig und auf die darauf gestützte Rüge der Beschwerdeführer ist folglich nicht einzutreten.
2. 2.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. Die Beschwerdeführer halten zudem allgemein die Überprüfung durch die Vollzugsbehörden für ungenügend. Das Amt für Umwelt habe nicht dargelegt, wie es seine Kontrollfunktion wahrnehme. Sie rügen weiter, dass die Vorinstanz einen Augenschein in der Steuerzentrale von Orange und beim Amt für Umwelt ebenso abgelehnt habe wie die Einsichtnahme in die Senderdatenbank des Bundesamts für Kommunikation (BAKOM). Darin erblicken sie eine Verletzung ihres Anspruchs auf rechtliches Gehör.
2.2 Die Qualitätssicherungssysteme dienen der Kontrolle, dass die bewilligten Parameter (äquivalente Strahlungsleistung ERP, Senderichtung) der Mobilfunkantennen im Betrieb eingehalten und die Grenzwerte der Verordnung vom 23. Dezember 1999 über den Schutz vor nichtionisierender Strahlung (NISV; SR 814.710) nicht überschritten werden. Diese Kontrolle ist in Art. 12 NISV 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.
Vor dem Hintergrund dieser Rechtsprechung durfte die Vorinstanz willkürfrei davon ausgehen, dass sich aus einem Augenschein keine relevanten zusätzlichen Erkenntnisse ergeben würden. Die Rüge der Verletzung des rechtlichen Gehörs (Art. 29 Abs. 2 BV) erweist sich damit ebenfalls als unbegründet.
In Bezug auf die von den Behörden durchgeführten Kontrollen legen die Beschwerdeführer schliesslich nicht hinreichend dar, weshalb sie davon ausgehen, diese seien unzuverlässig. Auf die diesbezügliche Kritik ist nicht einzutreten (Art. 42 Abs. 2 BGG).
3. 3.1 Die Beschwerdeführer rügen, die Visiere für den geplanten Antennenmast seien mehrmals versetzt worden. Sinngemäss rügen sie eine willkürliche Anwendung von § 88 Abs. 1 des kantonalen Planungs- und Baugesetzes vom 16. August 1995 (RB 700; im Folgenden: PBG). § 88 PBG hat folgenden Wortlaut:
1 Vor Einreichung des Baugesuchs sind Visiere aufzustellen, die den Standort und das Ausmass des Vorhabens bezeichnen.
2 Die Visiere sind bis zum rechtskräftigen Entscheid über das Baugesuch zu belassen.
3.2 Das Verwaltungsgericht hält dazu fest, die Visiere seien unbestrittenermassen bis zum Abschluss des Baubewilligungs- bzw. Einspracheverfahrens korrekt aufgestellt gewesen. Dass sie vor Abschluss des Rechtsmittelverfahrens wieder entfernt bzw. in der Zwischenzeit offensichtlich leicht verschoben auf der Liegenschaft Romanshornerstrasse 134 (recte: Hauptstrasse 134), jedoch ebenfalls an der Grenze zur Liegenschaft Romanshornerstrasse 132 (recte: Hauptstrasse 132) wieder aufgestellt wurden, entspreche zwar nicht der Vorgabe von § 88 Abs. 2 PBG. Dies ändere jedoch nichts daran, dass sich die potentiell betroffenen Anwohnerinnen und Anwohner, so insbesondere auch die Beschwerdeführer, über den Standort und die Dimensionen der zu erstellenden Mobilfunkanlage ein korrektes Bild machen konnten. Dies entspreche dem Sinn und Zweck der Visierungspflicht gemäss § 88 Abs. 1 PBG.
3.3 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 (BGE 133 I 149 E. 3.1 S. 153; 131 I 467 E. 3.1 S. 473 f.; je mit Hinweisen).
3.4 Die Auslegung von § 88 PBG durch die Vorinstanz lässt keine Willkür erkennen. Die Errichtung des Visiers (Baugespann) soll das Bauvorhaben veranschaulichen. Es gibt dem Nachbarn einen Hinweis auf mögliche Beeinträchtigungen durch die Baute. Dieser darf sich darauf verlassen, dass die wesentlichen Abmessungen ersichtlich sind. Über den exakten Umfang und die präzise Lage kann sich der Nachbar dagegen mit Hilfe der öffentlich aufliegenden Pläne orientieren (§ 89 PBG). Gemäss den für das Bundesgericht verbindlichen Feststellungen der Vorinstanz (Art. 105 Abs. 1 BGG) erfolgte die Entfernung nur vorübergehend und war die Verschiebung minimal. Hinzu kommt, dass nicht ersichtlich ist und von den Beschwerdeführern auch nicht geltend gemacht wird, dass sie durch die mangelhafte Profilierung in ihrer Interessenwahrnehmung beeinträchtigt worden sind. Eine Aufhebung des angefochtenen Entscheids und die damit verbundene Notwendigkeit der erneuten Aussteckung erschiene als formalistischer Leerlauf (vgl. BGE 133 I 201 E. 2.2 S. 204 f.; Urteil 1C_506/2008 vom 12. Mai 2009 E. 2.2.1; je mit Hinweisen). Die Rüge der willkürlichen Anwendung von § 88 Abs. § 1 PBG erweist sich somit als unbegründet.
4. 4.1 Nach Ansicht der Beschwerdeführer liegen genügend wissenschaftliche Studien vor, die nachweisen, dass die Grenzwerte der NISV zu hoch angesetzt sind. Letztere würden die nichtthermischen Wirkungen nichtionisierender Strahlung unberücksichtigt lassen und elektrosensible Personen unzureichend schützen. Die Beschwerdeführer kritisieren zudem, das BAFU sei bei der Evaluation wissenschaftlicher Studien zu streng, und berufen sich auf das Vorsorgeprinzip (Art. 74 Abs. 2 Satz 1 BV; Art. 1 Abs. 2 und Art. 11 Abs. 2 USG [SR 814.01]).
4. 4.1 Nach Ansicht der Beschwerdeführer liegen genügend wissenschaftliche Studien vor, die nachweisen, dass die Grenzwerte der NISV zu hoch angesetzt sind. Letztere würden die nichtthermischen Wirkungen nichtionisierender Strahlung unberücksichtigt lassen und elektrosensible Personen unzureichend schützen. Die Beschwerdeführer kritisieren zudem, das BAFU sei bei der Evaluation wissenschaftlicher Studien zu streng, und berufen sich auf das Vorsorgeprinzip (Art. 74 Abs. 2 Satz 1 BV; Art. 1 Abs. 2 und Art. 11 Abs. 2 USG [SR 814.01]).
4.2 4.2.1 Die Anlage- und Immissionsgrenzwerte der NISV hat das Bundesgericht bisher stets als gesetzes- und verfassungskonform beurteilt (Urteile 1C_492/2009 vom 20. Juli 2010 E. 2; 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 9. Oktober 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_492/2009 vom 20. Juli 2010 E. 2.2.1 mit Hinweis).
4.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_492/2009 vom 20. Juli 2010 E. 2.2.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 9. Oktober 2010]).
4.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 BGE 126 II 399 E. 3b S. 402 f.; SCHRADE/LORETAN, in: Kommentar zum Umweltschutzgesetz, 2. Aufl. 2002, N. 9 zu Art. 13 USG, vgl. auch N. 38 zu Art. 11 USG). 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 (Art. 11 Abs. 2 USG; BGE 133 II 169 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 (BGE 126 II 399 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.
4.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 Luxemburg und Belgien. Hierzu legt das BAFU dar, in Luxemburg werde für Mobilfunkantennen ein Vorsorgewert von 3 V/m angewendet. Dieser gelte jedoch - im Unterschied zu den Anlagegrenzwerten der NISV - nicht pro Anlage, sondern pro Antenne. Bei Anlagen mit mehreren Antennen, was die Regel sei, sei deshalb eine Kumulation der Strahlung zulässig. 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. Das BAFU geht schliesslich auch auf die von den Beschwerdeführern erwähnte Empfehlung der Europäischen Umweltagentur (EUA) ein und weist darauf hin, dass diese keine Empfehlungen für einen niedrigeren Grenzwert abgegeben habe.
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. Dies gilt auch in Bezug auf die von den Beschwerdeführern speziell erwähnten elektrosensiblen Personen. Weder gibt es zurzeit allgemein anerkannte Kriterien für eine objektive Diagnose von Elektrosensibilität noch konnte ein kausaler Zusammenhang zwischen elektromagnetischen Feldern und den mit Elektrosensibilität assoziierten Gesundheitsbeschwerden nachgewiesen werden (Urteil 1A.218/2004 vom 29. November 2005; BAFU, a.a.O., S. 93 ff.). 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.
5. 5.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.
5.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_492/2009 vom 20. Juli 2010 E. 3; 1C_316/2007 vom 30. April 2008 E. 9; 1A.129/2006 vom 10. Januar 2007 E. 4, nicht publ. in: BGE 133 II 64; 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 9. Oktober 2010]). Die Beschwerdeführer vermögen diese Befunde nicht in Frage zu stellen. Ihr Antrag ist abzuweisen.
6. 6.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 Besmerstrasse sichtbar. 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. Unmittelbar anschliessend an die Standortliegenschaft befänden sich zudem vier historische Bauten, die zusammen eine Baugruppe als Zeitdokument bildeten und durch den neuen "NHG-Richtplan" besonders geschützt seien. Der optisch herausragende Antennenmast beeinträchtige das Erscheinungsbild der vier Gebäude erheblich. 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 (Art. 9 BV).
In verfahrensrechtlicher Hinsicht machen die Beschwerdeführer in diesem Zusammenhang eine Verletzung des Anspruchs auf rechtliches Gehör geltend (Art. 29 Abs. 2 BV). Das Verwaltungsgericht habe keine Interessenabwägung zwischen den Belangen des Denkmal- und Ortsbildschutzes und den Interessen der Beschwerdegegnerin vorgenommen.
6.2 Der Hinweis der Beschwerdeführer auf den besonderen Schutz von vier Gebäuden im Anschluss an die Standortliegenschaft der geplanten Antenne ist als neue Tatsache im Sinne von Art. 99 Abs. 1 BGG nicht zulässig (vgl. E. 1.7 hiervor). Im Übrigen weist die Vorinstanz in ihrer Vernehmlassung darauf hin, dass das Ensemble bei den Erwägungen zum Ortsbild berücksichtigt worden sei.
6.3 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. BGE 131 II 545 E. 2.2 S. 547 f. mit Hinweisen; Urteile 1C_492/2009 vom 20. Juli 2010 E. 5.2; 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.
6.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 Art. 3 Abs. 1 NHG genannten Schutzobjekte verpflichtet sind (BGE 131 II 545 E. 2.2 S. 547 f. mit Hinweisen). Art. 3 NHG 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).
Die Vorinstanz führt aus, sowohl aus den Fotomontagen der Beschwerdeführer wie auch aus den Fotos zum Augenscheinprotokoll des Departements für Bau und Umwelt gehe hervor, dass dem Standortgebäude selbst ein erheblich stärkeres optisches Gewicht zukomme als der darauf geplanten Antenne. Eine relevante Beeinträchtigung des Erscheinungsbildes des Schutzobjektes "Blaues Haus" sei nicht ersichtlich. Die Stellungnahme des Amts für Denkmalpflege vom 23. Februar 2009 sei ohne weiteres nachvollziehbar. Nachdem weder in denkmal- noch in ortsbildschutzrechtlicher Hinsicht eine Beeinträchtigung von Schutzobjekten, namentlich des "Blauen Hauses", festzustellen sei, erübrige sich auch eine Interessenabwägung.
Die Einschätzung der Vorinstanz ist im Resultat 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. Ob vor diesem Hintergrund von einer lediglich marginalen Beeinträchtigung des Ortsbilds und des unter Schutz gestellten "Blauen Hauses" zu sprechen ist, oder - wie dies die Vorinstanz getan hat - eine Beeinträchtigung überhaupt verneint werden kann, ist nicht entscheidend und kann offen gelassen werden. Jedenfalls überwiegt das Interesse an einer leistungsfähigen Mobilfunkversorgung. 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 (vgl. dazu etwa Urteil 1A.6/2007 vom 6. September 2007 E. 4.3, in: URP 2008 S. 341). Es kann schliesslich auch nicht gesagt werden, die Vorinstanz sei ihrer Begründungspflicht nicht nachgekommen, zumal sie die für ihren Entscheid wesentlichen Punkte dargelegt hat. Die betreffenden Ausführungen ermöglichten es den Beschwerdeführern, sich über die Tragweite des Entscheids Rechenschaft abzulegen und ihn sachgemäss anzufechten.
6.5 Zusammenfassend ergibt sich, dass die Vorinstanz weder Art. 39 des kommunalen Baureglements willkürlich angewendet noch das Bundesgesetz über den Natur- und Heimatschutz verletzt hat und zudem ihrer Begründungspflicht nach Art. 29 Abs. 2 BV nachgekommen ist. Die diesbezüglichen Rügen der Beschwerdeführer sind unbegründet.
7. 7.1 Die Beschwerdeführer beanstanden, dass das Verwaltungsgericht der Beschwerdegegnerin eine Parteientschädigung von Fr. 300.-- zugesprochen hat. Sie halten diesen Betrag angesichts des Aufwands der Beschwerdegegnerin für ungerechtfertigt und machen sinngemäss eine willkürliche Anwendung von § 80 des Gesetzes des Kantons Thurgau vom 23. Februar 1981 über die Verwaltungsrechtspflege (BR 170.1; im Folgenden: VRG) geltend. Ausseramtliche Kosten könnten gemäss dieser Bestimmung nur zugesprochen werden, wenn sich dies bei komplizierter Sachlage oder schwierigen Rechtsfragen rechtfertige. § 75 des Gesetzes des Kantons Thurgau vom 6. Juli 1988 über die Zivilrechtspflege (Zivilprozessordnung; BR 271) sehe zudem vor, dass nur Ersatz für verursachte und notwendige Kosten zu leisten sei. Der Betrag von Fr. 300.-- würde über einen Ersatz der Auslagen im Sinne von Versandkosten, Porti und allfälligen Spesen weit hinausgehen.
7.2 § 80 Abs. 1 bis 3 VRG hat folgenden Wortlaut:
1 Im Verfahren vor dem Verwaltungsgericht oder dem Regierungsrat besteht in der Regel Anspruch auf Ersatz der ausseramtlichen Kosten.
2 Stehen sich in einem Rekursverfahren Privatparteien gegenüber, hat die obsiegende Privatpartei in der Regel Anspruch auf Ersatz der ausseramtlichen Kosten durch die unterliegende Privatpartei. Im Übrigen wird Ersatz ausseramtlicher Kosten nur zugesprochen, wenn sich dies bei komplizierter Sachlage oder schwierigen Rechtsfragen rechtfertigt.
3 Wird Ersatz ausseramtlicher Kosten zugesprochen, sind die unterliegende Partei oder das unterliegende Gemeinwesen zur Bezahlung der Entschädigung verpflichtet. § 75 der Zivilprozessordnung wird sinngemäss angewendet.
Das Verwaltungsgericht hielt zur Anwendung dieser Bestimmung im angefochtenen Entscheid fest, die Beschwerdegegnerin habe grundsätzlich Anspruch auf Ersatz ihrer ausseramtlichen Kosten. Da ihr Rechtsvertreter indessen von ihr angestellt sei, werde nur eine Entschädigung im Sinne eines Ersatzes von Auslagen zugesprochen.
7.3 Aus dem Wortlaut von § 80 VRG geht nicht hervor, dass im Falle der Vertretung durch einen (arbeitsvertraglich) Angestellten der obsiegenden Partei nur ein Ersatz der Auslagen zuzusprechen ist. Umso weniger erscheint als willkürlich, wenn das Verwaltungsgericht zwar nur einen Ersatz der Auslagen zuspricht, diesen aber relativ grosszügig bemisst und in der Form einer Pauschale, ohne detaillierte Kostenrechnung gewährt. Die Rüge der willkürlichen Anwendung von § 80 VRG ist demnach unbegründet.
8. Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Diesem Ausgang des Verfahrens entsprechend sind die Gerichtskosten den unterliegenden Beschwerdeführern aufzuerlegen (Art. 66 Abs. 1 BGG). Sie haben der obsiegenden, anwaltlich vertretenen Beschwerdegegnerin eine dem Aufwand entsprechende Parteientschädigung zu bezahlen (Art. 68 Abs. 2 BGG).
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 und dem Bundesamt für Umwelt schriftlich mitgeteilt.
Lausanne, 20. Oktober 2010
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Der Gerichtsschreiber:
Aemisegger Dold