Sachverhalt:
A.
A.a. Am 6. Mai 2013 reichte die Swisscom (Schweiz) AG ein Baugesuch für die Erstellung einer Mobilfunkanlage auf der Liegenschaft Nr. 1182 im Grundbuch Kreuzlingen an der Hauptstrasse 63 in Kreuzlingen ein. Auf dem Grundstück befindet sich ein Einkaufszentrum ("CEHA-Gebäude"). Die Antennenanlage ist an der nördlichen Seite des Gebäudes geplant und würde mit einer Höhe von 13,21 m die Gebäudehöhe um 9,68 m überragen. Gemäss dem Amt für Umwelt des Kantons Thurgau (AfU) erfüllt das Projekt die Anforderungen an den Immissionsschutz nach den bundesrechtlichen Vorgaben. Das kantonale Amt für Denkmalpflege gab hingegen eine negative Stellungnahme ab. Während der öffentlichen Auflage vom 15. Oktober bis 4. November 2013 gingen verschiedene Einsprachen ein, unter anderem von A._ und B._. Am 17. Februar 2015 lehnte die Politische Gemeinde Kreuzlingen das Baugesuch aus Gründen des Ortsbildschutzes ab.
A.b. Dagegen führte die Swisscom AG Rekurs beim Departement für Bau und Umwelt des Kantons Thurgau. Dieses stellte den Einsprechern am 12. Mai 2015 eine Kopie der Rekursschrift zu und räumte ihnen die Gelegenheit ein, sich am Verfahren zu beteiligen und eine allfällige Stellungnahme bis zum 5. Juni 2015 einzureichen bzw. bei einem Verzicht auf Vernehmlassung mitzuteilen, ob sie sich am Verfahren beteiligen möchten. Mit Schreiben vom 4. Juni 2015 teilten A._ und B._ dem Departement mit, dass sie angesichts des für sie günstigen Entscheids der Gemeinde auf eine Teilnahme am Rekursverfahren verzichten würden, allerdings unter dem Vorbehalt, sich später gegebenenfalls am Verfahren vor dem Verwaltungsgericht beteiligen zu können; gleichzeitig ersuchten sie um Zustellung des Rekursentscheides. Gemäss einer Aktennotiz vom 5. Juni 2015 führte die zuständige Sachbearbeiterin mit A._, die auch B._ vertrat, ein Telefongespräch, worin sie darauf hinwies, dass ohne Verfahrensbeteiligung kein Entscheid zugestellt werde und eine Teilnahme vor Verwaltungsgericht "vermutlich nicht möglich" sei. Mit Entscheid vom 30. November 2015 hiess das Departement den Rekurs gut und wies die Politische Gemeinde Kreuzlingen an, die Baubewilligung zu erteilen. Zur Begründung wurde im Wesentlichen ausgeführt, das öffentliche Interesse an hochqualitativen und wettbewerbsfähigen Fernmeldediensten überwiege die denkmalpflegerischen Interessen, die durch das Bauprojekt nicht stark beeinträchtigt würden.
Der Departementsentscheid wurde denjenigen Einsprechern, die auf eine Teilnahme am Verfahren verzichtet hatten, wie angekündigt nicht zugestellt. Am 29. Februar 2016 erteilte die Politische Gemeinde Kreuzlingen die Baubewilligung für die strittige Mobilfunkanlage. Diese wurde von den Einsprechern beim Departement angefochten.
B.
Am 21. Juni 2016 erhoben verschiedene Einsprecher, darunter A._ und B._, alle vertreten durch A._, Beschwerde beim Verwaltungsgericht des Kantons Thurgau gegen den Rekursentscheid vom 30. November 2015, von dem sie erst während des Rekursverfahrens gegen die Baubewilligung vom 29. Februar 2016 Kenntnis erhalten hätten. Mit verfahrensleitender Verfügung vom 23. Juni 2016 beschränkte der Präsident des Verwaltungsgerichts das Beschwerdeverfahren einstweilen auf die Frage der Legitimation der Beschwerdeführenden. Am 23. November 2016 trat das Verwaltungsgericht mangels formeller Beschwer der Beschwerdeführenden auf die Beschwerde nicht ein.
C.
Mit Beschwerde vom 23. Januar 2017 an das Bundesgericht beantragen A._ und B._, den Nichteintretensentscheid des Verwaltungsgerichts aufzuheben und die Sache zur materiellen Beurteilung an dieses zurückzuweisen.
Die Swisscom AG verzichtete auf eine Stellungnahme. Das Departement für Bau und Umwelt des Kantons Thurgau beantragt die Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Das Amt für Umwelt des Kantons Thurgau liess sich nicht separat vernehmen. Das Verwaltungsgericht des Kantons Thurgau und die Politische Gemeinde Kreuzlingen schliessen auf Abweisung der Beschwerde.
Mit Eingabe vom 13. März 2017 äusserten sich A._ und B._ nochmals zur Sache.

Erwägungen:
1.
1.1. Angefochten ist ein kantonal letztinstanzlicher Gerichtsentscheid, mit dem auf eine Beschwerde von Einsprechern gegen einen behördlichen Entscheid im Zusammenhang mit der Erstellung einer Mobilfunkantenne nicht eingetreten wurde, weil sie sich nicht am vorangehenden Beschwerdeverfahren vor dem zuständigen Departement beteiligt hatten. Inhaltlicher Streitpunkt ist unter anderem die Tragweite der bundesrechtlichen Bestimmungen zum Heimatschutz sowie zum Schutz vor nichtionisierender Strahlung und damit Bundesverwaltungsrecht, dessen Anwendung im Rahmen der Beschwerde in öffentlich-rechtlichen Angelegenheiten zu beurteilen ist (<ref-law>). Tritt eine kantonale Rechtsmittelinstanz in einer bundesrechtlichen Materie gestützt auf kantonales Verfahrensrecht auf eine Beschwerde nicht ein, ist ihr Nichteintretensentscheid geeignet, die richtige Anwendung des Bundesrechts zu vereiteln. Die Rüge, das kantonale Verfahrensrecht sei in bundesverfassungs- oder bundesrechtswidriger Weise angewendet worden, kann mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vorgebracht werden (<ref-law>; <ref-ruling> E. 1.2 S. 251; Urteil des Bundesgerichts 1C_442/2007 vom 21. April 2008 E. 1).
1.2. Im hier massgeblichen ersten Verfahren vor dem Departement befasste sich dieses einzig mit der Streitfrage der Vereinbarkeit des Bauprojekts mit den Bestimmungen der Denkmalpflege. Der Departementsentscheid vom 30. November 2015 äussert sich jedenfalls nur zu dieser Frage. Auf die übrigen bau-, zonen- und immissionsschutzrechtlichen Gesichtspunkte geht er nicht ein. Soweit das Departement die Sache an die Gemeinde zurückgewiesen hat zur Erteilung der Baubewilligung, geht der departementale Entscheid darüber hinweg, dass über die übrigen Voraussetzungen der Baubewilligung noch gar nicht befunden wurde. Das Verwaltungsgericht wiederum beschränkte seinen Entscheid auf die Frage der Legitimation der Beschwerdeführenden im verwaltungsgerichtlichen Verfahren. Nur dazu liegt ein verwaltungsgerichtlicher Entscheid vor, und nur dies bildet Streitpunkt im bundesgerichtlichen Verfahren.
1.3. Daraus ergibt sich, dass das Baubewilligungsverfahren noch nicht abgeschlossen ist, weshalb es sich beim angefochtenen Entscheid um einen Zwischenentscheid handelt (vgl. <ref-law> e contrario). Dagegen steht die Beschwerde, von hier nicht einschlägigen Ausnahmen abgesehen, nur offen, wenn der Entscheid für die Beschwerdeführenden einen nicht wieder gutzumachenden Nachteil bewirken könnte. Ein solcher liegt darin, dass die Frage der ortsbildschutzrechtlichen Zulässigkeit des Bauprojekts mit dem Entscheid des Verwaltungsgerichts, sollte dieser Bestand haben, rechtskräftig und damit für den weiteren Verlauf des Baubewilligungsverfahrens verbindlich entschieden und unabänderlich würde. Die Beschwerdeführenden könnten sich in diesem Zusammenhang nicht mehr zur Wehr setzen. Ihre Rechtsposition in den übrigen, noch offenen Streitpunkten bleibt aber uneingeschränkt bestehen. Die Beschwerdeführenden erleiden jedoch insofern einen irreversiblen Nachteil, als sie mit ihren ortsbildschützerischen Einwänden vor den kantonalen Behörden nicht mehr gehört werden, sollte der angefochtene Entscheid rechtskräftig werden.
1.4. Die Beschwerdeführenden haben sich am vorinstanzlichen Verfahren beteiligt. Sie sind als Einsprechende durch den angefochtenen Entscheid, mit dem ihnen die Legitimation für das verwaltungsgerichtliche Verfahren abgesprochen wurde, besonders berührt. Überdies haben sie ein schutzwürdiges Interesse an der Aufhebung oder Änderung des angefochtenen Entscheides. Sie sind damit zur Beschwerdeführung vor dem Bundesgericht hinsichtlich der Eintretensfrage legitimiert (vgl. <ref-law>).
1.5. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (vgl. Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG).
1.6. Mit der Beschwerde an das Bundesgericht können insbesondere die Verletzung von Bundesrecht (<ref-law>) und die offensichtlich unrichtige Feststellung des Sachverhaltes (vgl. <ref-law>) gerügt werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), prüft die bei ihm angefochtenen Entscheide aber grundsätzlich nur auf Rechtsverletzungen hin, die von den Beschwerdeführern geltend gemacht und begründet werden (vgl. <ref-law>). Erhöhte Anforderungen an die Begründung gelten, soweit die Verletzung von Grundrechten (unter Einschluss von Willkür bei der Rechtsanwendung und bei der Sachverhaltsfeststellung) gerügt wird (<ref-law>; <ref-ruling> E. 1.4.2 S. 254 mit Hinweisen).
2.
2.1. Die Beschwerdeführenden erklären, sie hätten sich nicht am Beschwerdeverfahren vor dem Departement beteiligt, da die Gemeinde die Rechtmässigkeit der Erstellung der strittigen Mobilfunkanlage verneint hatte. Sie hätten damit sowohl mit Blick auf das Ergebnis des für sie günstigen Entscheids der Gemeinde als auch im Hinblick auf die Vermeidung allfälliger Kostenfolgen keinen Anlass gehabt, am departementalen Verfahren teilzunehmen. Sie hätten aber klar zu erkennen gegeben, dass sie sich eine Beteiligung an einem allfälligen verwaltungsgerichtlichen Verfahren vorbehalten würden, falls der Departementsentscheid zu ihren Ungunsten ausginge. Die Auffassung des Verwaltungsgerichts, sie hätten mit dem Verzicht im Verfahren vor dem Departement die Parteistellung und die Beschwerdeberechtigung im weiteren Rechtsmittelverfahren verloren, sei willkürlich, überspitzt formalistisch und verstosse gegen Treu und Glauben.
2.2. Jede Person hat in Verfahren vor Gerichts- und Verwaltungsinstanzen Anspruch auf gleiche und gerechte Behandlung, auf Beurteilung innert angemessener Frist sowie auf rechtliches Gehör (Art. 29 Abs. 1 und 2 BV).
2.2.1. Nach der bundesgerichtlichen Rechtsprechung begeht eine Behörde eine Gehörsverletzung im Sinne einer formellen Rechtsverweigerung, wenn sie auf eine ihr frist- und formgerecht unterbreitete Sache nicht eintritt, obschon sie darüber entscheiden müsste (<ref-ruling> E. 2.1 S. 9; <ref-ruling> E. 2.3 S. 232; vgl. auch <ref-ruling> E. 2.1). Ob eine solche Rechtsverweigerung vorliegt, prüft das Bundesgericht frei (<ref-ruling> E. 2a S. 142 mit Hinweisen). Die Auslegung und Anwendung des einschlägigen kantonalen Rechts untersucht es indessen nur unter dem Gesichtswinkel der Willkür (<ref-ruling> E. 2.1 S. 219, 467 E. 3.1 S. 473 f., je mit Hinweisen).
2.2.2. Gemäss der ständigen Praxis des Bundesgerichts ist ein Entscheid willkürlich, wenn er 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. 2.4 S. 5; <ref-ruling> E. 4.1 S. 133; je mit Hinweisen).
2.2.3. Überspitzter Formalismus als besondere Form der Rechtsverweigerung liegt vor, wenn für ein Verfahren rigorose Formvorschriften aufgestellt werden, ohne dass die Strenge sachlich gerechtfertigt wäre, wenn die Behörde formelle Vorschriften mit übertriebener Schärfe handhabt oder an Rechtsschriften überspannte Anforderungen stellt und damit dem Bürger den Rechtsweg in unzulässiger Weise versperrt (vgl. <ref-ruling> E. 4.2 S. 158; <ref-ruling> E. 2.1 S. 9; <ref-ruling> E. 5.4.1 S. 183 mit Hinweisen). Das Verbot des überspitzten Formalismus weist einen engen Bezug zum Grundsatz von Treu und Glauben (<ref-law>; dazu <ref-ruling> E. 2.5.1 S. 73; <ref-ruling> E. 6.1 S. 636 f.; <ref-ruling> E. 4.1 S. 170) auf. Nach der bundesgerichtlichen Praxis erscheint es überspitzt formalistisch, eine Prozesserklärung buchstabengetreu auszulegen, ohne zu fragen, welcher Sinn ihr vernünftigerweise beizumessen sei (<ref-ruling> E. 2 S. 96 f. mit Hinweisen). Parteierklärungen, die im Rahmen eines Prozesses abgegeben werden, sind unter Berücksichtigung von Treu und Glauben auszulegen (<ref-ruling> E. 2a S. 152 mit Hinweisen), d.h. sie müssen so ausgelegt werden, wie sie der Empfänger nach den gesamten Umständen in guten Treuen verstehen durfte und verstehen musste (<ref-ruling> E. 3b S. 58 mit Hinweisen). Dies gilt umso mehr, wenn es sich bei den Verfahrensbeteiligten - wie hier - um juristische Laien handelt (Urteil des Bundesgerichts 1C_442/2007 vom 21. April 2008 E. 2.1).
3.
3.1. Die Beschwerdeführenden nennen keine kantonale Bestimmung, die willkürlich angewendet worden sein soll. Hingegen sind sie der Ansicht, das Verwaltungsgericht habe den Sachverhalt "nicht berücksichtigt" und deswegen einen willkürlichen Entscheid gefällt. Das lässt sich als Rüge einer willkürlichen bzw. offensichtlich unrichtigen Sachverhaltsfeststellung verstehen. Indessen ist nicht ersichtlich, weshalb die tatsächlichen Feststellungen der Vorinstanz willkürlich sein sollten. Das Schreiben der Sachbearbeiterin und die Aktennotiz zum Telefonat sind aktenkundig, und das Verwaltungsgericht hat auch vom geäusserten Vorbehalt der Beschwerdeführenden Kenntnis genommen und diesen juristisch gewürdigt. Die Sachverhaltsfeststellungen im angefochtenen Entscheid sind mithin nicht offensichtlich unrichtig.
3.2. In rechtlicher Hinsicht ging das Verwaltungsgericht davon aus, es fehle den Beschwerdeführenden an der formellen Beschwer, weil sie sich nicht vorweg am Verfahren vor dem Departement beteiligt hatten. Die Voraussetzung der formellen Beschwer ist im schweizerischen Verwaltungsprozess verbreitet üblich (KIENER ET AL., Öffentliches Verfahrensrecht, 2. Aufl., 2015, 1427 ff.; RHINOW ET AL., Öffentliches Prozessrecht, 3. Aufl., 2014, Rz. 1099). Nach <ref-law> gilt sie ausdrücklich auch im bundesgerichtlichen Verfahren. Gemäss dem Grundsatz der Einheit des Verfahrens muss sich am Verfahren vor allen kantonalen Vorinstanzen beteiligen können, wer zur Beschwerde an das Bundesgericht berechtigt ist (<ref-law>). Dabei handelt es sich um einen allgemeinen verfahrensrechtlichen Grundsatz. Umgekehrt ergibt sich für die Beschwerdeführenden aus dem Prinzip der Einheit des Verfahrens grundsätzlich die Obliegenheit, sich am kantonalen Verfahren als Partei zu beteiligen, jedenfalls dann, wenn sie letztinstanzlich ans Bundesgericht gelangen wollen. Eine Ausnahme gilt, wenn jemand keine Möglichkeit zur Teilnahme am vorinstanzlichen Verfahren erhalten hat (Urteil des Bundesgerichts 1C_442/2007 vom 21. April 2008 E. 2.3). Die formelle Beschwer fehlt, wenn ein Beschwerdeführer von sich aus auf die Teilnahme am Verfahren vor der Vorinstanz verzichtet hat (KIENER ET AL., a.a.O., Rz. 1429; RHINOW ET AL., a.a.O., Rz. 1552). Es ist daher keineswegs systemfremd, willkürlich oder überspitzt formalistisch, wenn ein Kanton, wie dies vor Bundesgericht gilt, als Zulässigkeitsvoraussetzung für die Anrufung des Verwaltungsgerichts verlangt, dass sich am Verfahren vor den unteren Instanzen beteiligt haben muss, wer ein kantonales Rechtsmittel an das Verwaltungsgericht ergreifen will.
3.3. Genauso wenig läuft es auf übertriebene formelle Anforderungen hinaus, wenn die kantonalen Instanzen einen Vorbehalt nicht zulassen, unter Auslassung der Beteiligung an einer Verwaltungsinstanz dann später doch wieder am Verwaltungsgerichtsverfahren teilnehmen zu wollen, wenn dazwischen ein ungünstiger Entscheid ergeht. Wer sich aus dem Verfahren ausklinkt, tut das definitiv. Die Teilnahme am Verfahren ist in diesem Sinne bedingungsfeindlich. Es erscheint zwar verständlich, dass die Beschwerdeführenden im vorliegenden Fall, in dem die Gemeinde in ihrem Sinne entschieden hatte, ihren eigenen Aufwand sowie die allfälligen Kostenfolgen für die nachfolgenden Verfahrensstufen vermeiden wollten. Das rechtfertigt aber eine Nichtteilnahme unter Vorbehalt nicht. Das Kostenrisiko bildet Bestandteil des schweizerischen Justizsystems und soll dazu beitragen, aussichtslose Verfahren zu vermeiden. Dem hat sich zu stellen, wer in einen Prozess einsteigt. Als Ausgleich gibt es im Bedarfsfall unter den entsprechenden Voraussetzungen den verfassungsrechtlichen Anspruch auf unentgeltliche Rechtspflege für Bedürftige (vgl. <ref-law>), was hier allerdings nicht weiter von Belang ist.
3.4. Verletzt wurde im vorliegenden Fall auch nicht der Grundsatz von Treu und Glauben. Weder das Verwaltungsgericht noch das Departement haben durch ihre Handlungen eine entsprechende Vertrauensgrundlage geschaffen. Das Verwaltungsgericht äusserte sich nie dahingehend oder erzeugte auch nur den entsprechenden Anschein, den Vorbehalt der Beschwerdeführenden gelten zu lassen. Das Departement als Vorinstanz des Verwaltungsgerichts fragte die Beschwerdeführenden ausdrücklich an, ob sie sich beteiligten wollten. Es teilte ihnen überdies explizit mit, der departementale Entscheid würde ihnen bei einer Nichtteilnahme nicht zugestellt und eine erst spätere Teilnahme vor Verwaltungsgericht sei diesfalls "vermutlich nicht möglich". Gestützt darauf musste den Beschwerdeführenden klar sein, welches Risiko sie mit der Nichtbeteiligung eingingen. Eine Vertrauensgrundlage für die gegenteilige Annahme ist hingegen nicht ersichtlich.
3.5. Damit bleibt einzig noch zu klären, ob den Beschwerdeführenden durch den angefochtenen Entscheid die Gelegenheit genommen wurde, ihre sämtlichen Standpunkte und Argumente als Einsprecher vorzutragen.
3.5.1. In seinem Urteil 1C_442/2007 vom 21. April 2008 mit einer teilweise vergleichbaren Ausgangslage entschied das Bundesgericht, dass bei einem Teilnahmeverzicht nach vorerst, d.h. noch nicht letztinstanzlichem, günstigem Verfahrensausgang die Rechte als Einsprecher nicht gekürzt werden dürften. Im damaligen Fall hatte die Verwaltungsbehörde den Einsprechern eine Kopie der vom Mobilfunkanbieter und Bauherrn für (ebenfalls) eine Mobilfunkantenne erhobenen Beschwerde zugestellt mit Frist zur allfälligen Beteiligung am Beschwerdeverfahren unter Hinweis darauf, Stillschweigen gelte als Verzicht auf die Beteiligung. Die Einsprecher äusserten sich nicht zur Beschwerde, da die Gemeinde damals die Baubewilligung aus zonenplanerischen Gründen verweigert hatte, während sich die Einsprecher auf andere Argumente gestützt hatten. In der Folge erteilte die kantonale Verwaltungsbehörde direkt die Gesamtbaubewilligung. Das von den Einsprechern angerufene zuständige Verwaltungsgericht trat mangels Beschwer auf ihre Beschwerde nicht ein. Das Bundesgericht sah darin insbesondere einen Verstoss gegen <ref-law>, weil die Einsprecher ihre Anliegen überhaupt nicht mehr einbringen konnten bzw. ihre Einsprachen gar nie vollumfänglich behandelt worden waren.
3.5.2. Im vorliegenden Fall ist die Ausgangslage nicht dieselbe. Erstens hatten sich im Vergleichsfall die Einsprecher vor der kantonalen Verwaltungsbehörde einfach nicht geäussert bzw. keinen Antrag gestellt, woraus die kantonalen Behörden etwas fragwürdig auf eine generelle Nichtteilnahme am Verfahren schlossen. Demgegenüber verzichteten die Beschwerdeführenden hier auf Nachfrage hin ausdrücklich auf eine Teilnahme am Departementsverfahren. Zweitens erging im vorliegenden Fall noch keine Gesamtbaubewilligung. Mit dem angefochtenen Nichteintretensentscheid werden die Beschwerdeführenden einzig von der weiteren Geltendmachung ortsbildschützerischer Argumente ausgeschlossen, die für sie ursprünglich gar nicht im Vordergrund gestanden sind, beriefen sie sich doch in ihrer Einsprache hauptsächlich auf die immissions- und zonenrechtliche Rechtswidrigkeit des Bauprojekts. Die aktenkundige Einsprache der Beschwerdeführenden mit ihren untergeordneten Argumenten zum Ortsbildschutz lag im Übrigen dem zuständigen Departement vor und konnte von diesem berücksichtigt werden. Im Punkt des Ortsbildschutzes wird der Entscheid des Departements mit seiner Rechtskraft verbindlich und ist danach nicht mehr anfechtbar. Für die übrigen, insbesondere bau-, zonen- und immissionsrechtlichen, Streitpunkte ist der Verfahrensausgang nach der Rückweisung der Streitsache an die Gemeinde durch das Departement, das sich dazu nicht geäussert hat, jedoch noch offen. Den Einsprechern muss die Beteiligung am Verfahren insofern weiterhin offen stehen. Ihre Einsprachen sind in diesen Punkten zu behandeln, und die Beschwerdeführenden müssen sich insoweit auch noch ins Verfahren einbringen können.
3.5.3. Der Departementsentscheid mag diesbezüglich in seiner Begründung etwas missverständlich erscheinen, soweit darin in Erwägung 5, wenn auch nicht im Dispositiv, ausgeführt wird, die Gemeinde werde angewiesen, die Baubewilligung zu erteilen. Tatsächlich hatte die Gemeinde bei ihrem erneuten Baubewilligungsentscheid die Rechtslage, abgesehen von den ortsbildschützerischen Gesichtspunkten, die eine Verweigerung der Bewilligung nicht mehr zu begründen vermochten, umfassend, namentlich auf bau-, zonen- und immissionsrechtliche Zulässigkeit hin, zu prüfen und dabei auch die eingegangenen Einsprachen zu behandeln. Ob die Gemeinde in ihrem Entscheid vom 29. Februar 2016 diese Vorgaben eingehalten hat, ist hier nicht Streitobjekt. Für das vorliegende Verfahren ist jedenfalls davon auszugehen, dass die Rechte der Beschwerdeführenden als Einsprecher gewahrt sind. Diese haben denn auch gegen den Baubewilligungsentscheid der Gemeinde vom 29. Februar 2016 Rekurs erhoben, wobei das Rechtsmittelverfahren nach dem Kenntnisstand des Bundesgerichts noch hängig ist.
3.6. Der angefochtene Entscheid verstösst demnach nicht gegen Bundesrecht.
4.
Die Beschwerde erweist sich als unbegründet und ist abzuweisen.
Bei diesem Verfahrensausgang werden die unterliegenden Beschwerdeführenden unter Solidarhaft für das bundesgerichtliche Verfahren kostenpflichtig (Art. 66 Abs. 1, Art. 65 BGG). Eine Parteientschädigung ist nicht zuzusprechen.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführenden unter Solidarhaft auferlegt.
3.
Dieses Urteil wird den Parteien, der Stadt Kreuzlingen, dem Departement für Bau und Umwelt des Kantons Thurgau, dem Amt für Umwelt des Kantons Thurgau und dem Verwaltungsgericht des Kantons Thurgau schriftlich mitgeteilt.
Lausanne, 23. Juni 2017
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Merkli
Der Gerichtsschreiber: Uebersax