Sachverhalt:
A.
A._ und B._ als Eigentümer der Liegenschaft Nr. xxx im Grundbuch Tobel-Tägerschen/TG erhoben im Jahre 2013 Einsprache gegen ein Bauprojekt des Ehepaars C.D._ und D.D._ auf der nachbarschaftlichen Liegenschaft Nr. yyy. Am 4. November 2013 wies die Gemeinde Tobel-Tägerschen die Einsprache ab und erteilte die Baubewilligung. Dagegen erhoben A._ und B._ Rekurs beim Departement für Bau und Umwelt des Kantons Thurgau. Am 7. Januar 2014 beantragten die Ehegatten C.D._ und D.D._ bei der Gemeinde eine vorzeitige Baufreigabe, die am 15. Januar 2014 bewilligt wurde. Auch dagegen rekurrierten A._ und B._. Am 29. August 2014 wies das Departement beide Rekurse in einem einzigen Entscheid ab und auferlegte den Rekurrenten eine Verfahrensgebühr von insgesamt Fr. 2'500.--.
B.
Dagegen führten A._ und B._ Beschwerde beim Verwaltungsgericht des Kantons Thurgau, wobei sie nebst den Anträgen in der Sache ausdrücklich mit Blick auf die Anfechtung der vorzeitigen Baufreigabe zur Hälfte auch die Kostenauflage im Betrag von Fr. 1'250.-- anfochten. Mit Entscheid vom 4. Mai 2016 wies das Verwaltungsgericht die Beschwerde integral ab.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 4. Juli 2016 an das Bundesgericht beantragen A._ und B._, das Urteil des Verwaltungsgerichts aufzuheben und ihnen für das Verfahren betreffend vorzeitige Baufreigabe vor dem Departement keine Kosten aufzuerlegen bzw. diese auf das gesetzliche Minimum von Fr. 50.-- herabzusetzen. Zur Begründung machen sie im Wesentlichen geltend, das Departement habe im fraglichen Verfahren gar keinen Aufwand getätigt. Mit dem Entscheid in der Sache bzw. der vorzeitigen Realisierung des Bauprojekts sei der Rekurs gegen die Erteilung der vorzeitigen Baubewilligung gegenstandslos geworden. Eine Kostenauflage sei deshalb insbesondere mit Blick auf die für Gebühren massgeblichen Grundsätze wie das Kostendeckungs- und Äquivalenzprinzip willkürlich und rechtsungleich und verstosse auch gegen weitere Verfassungsrechte.
Das Departement für Bau und Umwelt des Kantons Thurgau, die Politische Gemeinde Tobel-Tägerschen und das Verwaltungsgericht des Kantons Thurgau schliessen auf Abweisung der Beschwerde. C.D._ und D.D._ reichten dem Bundesgericht keine Stellungnahme ein.
Mit Eingabe vom 22. September 2016 äusserten sich A._ und B._ nochmals zur Sache.

Erwägungen:
1.
1.1. Die Zulässigkeit der Beschwerde an das Bundesgericht im Kostenpunkt folgt derjenigen in der Hauptsache. Gemäss <ref-law> beurteilt das Bundesgericht Beschwerden in Angelegenheiten des öffentlichen Rechts. Dieses Rechtsmittel steht auch auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung (<ref-ruling> E. 1.2 S. 251; <ref-ruling> E. 1.1 S. 411). Da in Bezug auf die Hauptsache die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig wäre, steht sie auch im Kostenpunkt offen.
1.2. Beim angefochtenen Entscheid handelt es sich um einen anfechtbaren kantonal letztinstanzlichen Endentscheid (vgl. Art. 86 Abs. 1 lit. d und Art. 90 BGG).
1.3. Die Beschwerdeführer sind als Kostenpflichtige und als direkte Adressaten des angefochtenen Entscheids gemäss <ref-law> zur Beschwerde legitimiert.
1.4. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist daher weder an die in der Beschwerde vorgebrachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann die Beschwerde aus einem anderen als dem angerufenen Grund gutheissen, und es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (Motivsubstitution; <ref-ruling> E. 1 S. 236 mit Hinweisen).
2.
Die Beschwerdeführer beanstanden den Einbezug der Gemeinde ins bundesgerichtliche Verfahren und machen geltend, deren Stellungnahme dürfe nicht berücksichtigt werden, da sie im Kostenpunkt gar nicht mehr betroffen sei. Auf diese Frage braucht nicht weiter eingegangen zu werden, weil sich die Ausführungen der Gemeinde als nicht entscheidwesentlich erweisen.
3.
3.1. Die Kostenverteilung im kantonalen Rechtsmittelverfahren richtet sich mangels bundesrechtlicher Vorschriften nach kantonalem Recht, dessen Anwendung das Bundesgericht nur daraufhin überprüft, ob dadurch Bundesrecht mit Einschluss der Bundesverfassung verletzt ist (<ref-law>). Dazu gehören namentlich die willkürliche Anwendung kantonalen Rechts (<ref-law>) sowie das Rechtsgleichheitsgebot (<ref-law>), aber auch die übrigen verfassungsmässigen Rechte und Grundsätze.
3.2. Gemäss der ständigen Praxis des Bundesgerichts ist ein Entscheid willkürlich gemäss <ref-law>, 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).
3.3. Ein Entscheid verstösst gegen das Gebot der Rechtsgleichheit nach <ref-law>, wenn er rechtliche Unterscheidungen trifft, für die ein vernünftiger Grund nicht ersichtlich ist, oder Unterscheidungen unterlässt, die sich aufgrund der Verhältnisse aufdrängen. Das Rechtsgleichheitsgebot ist insbesondere verletzt, wenn Gleiches nicht nach Massgabe seiner Gleichheit gleich oder Ungleiches nicht nach Massgabe seiner Ungleichheit ungleich behandelt wird (vgl. <ref-ruling> E. 3.3.2 S. 127; <ref-ruling> E. 5 S. 192).
3.4. Verfahrenskosten sind wie Gerichtskosten Kausalabgaben, weshalb sie dem verfassungsmässigen Kostendeckungs- und Äquivalenzprinzip genügen müssen. Das Kostendeckungsprinzip besagt, dass der Gebührenertrag die gesamten Kosten des betreffenden Verwaltungszweigs nicht oder nur geringfügig übersteigen soll. Für allgemeine administrative Verfahrenskosten spielt dies im Allgemeinen gleich wie für Gerichtsgebühren keine Rolle, decken doch erfahrungsgemäss diese Gebühren die entsprechenden Kosten bei Weitem nicht. Das Äquivalenzprinzip konkretisiert das Verhältnismässigkeitsprinzip (<ref-law>) und das Willkürverbot (<ref-law>) für den Bereich der Kausalabgaben. Es bestimmt, dass eine Gebühr nicht in einem offensichtlichen Missverhältnis zum objektiven Wert der Leistung stehen darf und sich in vernünftigen Grenzen halten muss. Bei der Festsetzung solcher Gebühren verfügt die Behörde über einen grossen Ermessensspielraum (vgl. <ref-ruling> E. 3.3.2 S. 108 f.).
3.5. Nach § 110 Abs. 2 des thurgauischen Planungs- und Baugesetzes vom 21. Dezember 2011 (PBG; RB 700) kann die Gemeindebehörde nach Ablauf der Einsprachefrist in Abwägung der beteiligten Interessen einen vorzeitigen Baubeginn bewilligen, sofern dadurch die Entscheidungsfreiheit in Einsprache- und Rechtsmittelverfahren nicht beeinträchtigt wird; ein Rekurs gegen die Bewilligung des vorzeitigen Baubeginns hat keine aufschiebende Wirkung, unter Vorbehalt der Wiedererteilung durch die Rekursinstanz.
3.6. Gemäss § 77 des Gesetzes vom 23. Februar 1981 des Kantons Thurgau (VRG; RB 170.1) trägt in streitigen Verfahren in der Regel der Unterliegende die Kosten. Bei teilweisem Unterliegen ist der entsprechende Kostenanteil aufzuerlegen. Nach § 78 VRG gehen Kosten zulasten eines Beteiligten, soweit dieser sie insbesondere durch Verletzung wesentlicher Verfahrensvorschriften oder durch ungehöriges Verhalten verursacht hat. Gemäss § 9 Abs. 1 Ziff. 2 der Verordnung des Grossen Rates des Kantons Thurgau vom 16. Dezember 1992 über die Gebühren der kantonalen Verwaltungsbehörden (nachfolgend: Gebührenverordnung; RB 631.1) betragen die Verfahrensgebühren der Departemente Fr. 50.-- bis Fr. 2'500.--.
4.
4.1. Nach Ansicht der Beschwerdeführer ist das Argument des Verwaltungsgerichts im angefochtenen Entscheid fragwürdig, sie hätten eine Verfahrensverzögerung geltend machen müssen, nachdem das Bauprojekt aufgrund der vorzeitigen Baubewilligung rasch realisiert worden war und eine Verzögerungsbeschwerde möglicherweise von vornherein nutzlos erschienen wäre. Wie es sich damit verhält, kann jedoch offenbleiben, da die vorliegende Beschwerde jedenfalls aus anderen Gründen erfolglos bleiben muss (vgl. E. 1.4).
4.2. Entgegen der Auffassung der Beschwerdeführer vereinigte das Departement die beiden bei ihm hängigen Verfahren im Zusammenhang mit dem damals strittigen Baugesuch, d.h. dasjenige in der Sache über die Baubewilligung als solcher als auch dasjenige über die Erteilung der vorzeitigen Baubewilligung unter Einschluss der von den Beschwerdeführern beantragten Wiedererteilung der aufschiebenden Wirkung. Das geht nicht zuletzt aus der entsprechenden ausdrücklichen Dispositivziffer 1 des Departementsentscheides vom 29. August 2014 hervor. In einem Entscheid wurden demnach vom Departement verschiedene Streitpunkte aus zwei Rekursen beurteilt. Das Departement sprach einen gesamthaften Kostenentscheid und setzte den Betrag auf das Maximum des zulässigen Gebührenrahmens fest.
4.3. Erneut entgegen der Auffassung der Beschwerdeführer war das Departement im Streitpunkt der vorzeitigen Baubewilligung nicht untätig geblieben. Es hatte aufgrund des entsprechenden Rekurses einen eigenen Schriftenwechsel durchgeführt. Im Rekursentscheid befasste es sich in drei Erwägungsziffern über mehr als zwei Seiten mit der Frage der vorzeitigen Baubewilligung. Insofern kam es zum nicht mehr strittigen Schluss, dass der entsprechende Rekurs teilweise gegenstandslos geworden, teilweise aber auch abzuweisen war. Der fragliche Rekurs ist nicht wegen Untätigkeit der Behörde dahingefallen, wie die Beschwerdeführer meinen, sondern beruhte auf dem Unterliegen der Beschwerdeführer mit ihren entsprechenden Anträgen (vgl. § 77 VRG). Eine Verletzung wesentlicher Verfahrensvorschriften oder grobe Fehler im Sinne von ungehörigem Verhalten gemäss § 78 VRG sind dem Departement nicht vorzuwerfen.
4.4. Angesichts des den Behörden zustehenden Ermessens bei der Kostenfestlegung verstiess es nicht in unhaltbarer Weise gegen die gesetzlichen Bestimmungen des Kantons Thurgau über die Kostenverteilung in departementalen Verfahren, den Beschwerdeführern eine integrale Verfahrensgebühr von Fr. 2'500.-- aufzuerlegen, die namentlich auch das Rekursverfahren im Zusammenhang mit der vorzeitigen Baubewilligung erfasste. Obwohl damit der obere Rand des Gebührenrahmens erreicht wird (vgl. § 9 Abs. 1 Ziff. 2 Gebührenverordnung), erscheint die konkret festgesetzte und den Beschwerdeführern auferlegte Gebühr angesichts des Umstands, dass es sich um ein vereinigtes Verfahren handelte und dass beim Departement auch im Streitpunkt der vorzeitigen Baubewilligung Aufwand angefallen war, vertretbar. Die Gebühr verstösst auch nicht gegen das Äquivalenzprinzip.
4.5. Demnach ist der angefochtene Entscheid nicht willkürlich oder rechtsungleich noch verletzt er andere verfassungsmässige Rechte der Beschwerdeführer wie insbesondere die von diesen ebenfalls angerufene Eigentumsgarantie nach <ref-law> oder den Anspruch auf ein faires Verfahren gemäss <ref-law>.
5.
Die Beschwerde erweist sich als unbegründet und ist abzuweisen.
Bei diesem Verfahrensausgang werden die Beschwerdeführer für das bundesgerichtliche Verfahren unter Solidarhaft kostenpflichtig (Art. 66 Abs. 1 und 5, <ref-law>). 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ührern unter Solidarhaft auferlegt.
3.
Dieses Urteil wird den Parteien, der Politischen Gemeinde Tobel-Tägerschen, dem Departement für Bau und Umwelt des Kantons Thurgau und dem Verwaltungsgericht des Kantons Thurgau schriftlich mitgeteilt.
Lausanne, 14. Oktober 2016
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Uebersax