Sachverhalt: A. A.a. A.A._ und B.A._ sowie C.C._ und D.C._ sind Eigentümer zweier benachbarten Liegenschaften auf den Parzellen Nr. aaaa bzw. Nr. cccc in Frauenfeld. Die beiden Liegenschaften grenzen aneinander und sind beide der Wohnzone W3 und dem Perimeter des Arealüberbauungsplans "Wohnpark X._" aus dem Jahre 1994 zugewiesen. Die Gärten der beiden Liegenschaften sind nach Westen ausgerichtet, wobei das Grundstück der Eheleute C._ südlich an dasjenige der Eheleute A_ grenzt. A.b. Am 3. Oktober 2008 reichten die Eheleute C._ ein Baugesuch für eine Gartengestaltung ein. Dabei sahen sie im Wesentlichen die Errichtung eines Aussensitzplatzes in Form eines Terrassenpodestes vor, das sich auf einem 50 cm hohen und eine Grundfläche von 3.50 x 5.00 m aufweisenden Holzdeck befinden sollte. Das Podest sollte mit Ausnahme des über drei Treppenstufen erfolgenden Zuganges von einer das Holzdeck um 10 cm überragenden Mauer umfasst werden. Da das Holzpodest bei einem Mindestgrenzabstand von drei Metern gemäss dem Baureglement der Politischen Gemeinde Frauenfeld lediglich einen Abstand von einem Meter zur gemeinsamen Grenze mit der Parzelle der Eheleute A._ aufwies, ersuchten die Eheleute C._ ihre Nachbarn um ein Näherbaurecht. A.A._ und B.A._ unterzeichneten am 19. Oktober 2008 eine Vereinbarung über die Herabsetzung des Grenzabstandes für die auf der Parzelle Nr. cccc projektierte Baute/Anlage gemäss der Baueingabe. Am 20. Oktober 2008 unterzeichnete einer der beiden Miteigentümer der Liegenschaft der Familie A._ (gemäss Darstellung der Eheleute A._ handelte es sich dabei um A.A._) den Baugesuchsplan "Bauprojekt Gartengestaltung" vom 3. Oktober 2008. Der Stadtrat der Politischen Gemeinde Frauenfeld erteilte C.C._ und D.C._ am 28. Oktober 2008 die Baubewilligung für die vorgesehene Gartengestaltung, welche in der Folge auch realisiert wurde. A.c. Im März 2009 verlangten die Eheleute A._ vom Stadtrat Frauenfeld den Rückbau einer auf dem Grundstück von C.C._ und D.C._ erstellten Beschattungsanlage, da für diese kein Baugesuch eingereicht worden sei und die Sonnenstore sowohl den Grenzabstand verletze als auch Schatten auf das Grundstück der Eheleute A._ werfe. Am 29. Dezember 2009 reichten A.A._ und B.A._ beim Bezirksgericht Frauenfeld eine zivilrechtliche Klage ein, mit welcher im Wesentlichen verlangt wurde, es sei die Unverbindlichkeit der zwischen den Parteien am 19. Oktober 2008 geschlossenen Vereinbarung betreffend Herabsetzung des Grenzabstandes wegen Grundlagenirrtums und absichtlicher Täuschung festzustellen. Mit Urteil vom 24. März 2010 wies das Bezirksgericht Frauenfeld die Klage ab, was das Obergericht des Kantons Thurgau auf Berufung hin mit Urteil vom 16. Dezember 2010 bestätigte. Nach Durchführung eines Baubewilligungsverfahrens mit anschliessendem Rekursverfahren zogen C.C._ und D.C._ das Baugesuch für die Beschattungsanlage zurück und stellten diesbezüglich den ursprünglichen Zustand wieder her. B. Im Rekursverfahren betreffend Beschattungsanlage hatten die Eheleute A._ erstmals auch geltend gemacht, die Ausführung der Gartenanlage entspreche nicht der Baubewilligung. Mit Schreiben vom 4. August 2011 und 5. September 2011 verlangten sie vom Stadtrat Frauenfeld den Erlass eines anfechtbaren Entscheides, da das im Garten erstellte Podest und die das Podest umgebende Mauer sechs cm höher seien als bewilligt. Zudem sei ein nicht bewilligter Holzrost verlegt worden. Ausserdem wurde eine Anpassung des Grundbucheintrages zum Näherbaurecht beantragt. Mit Beschluss vom 13. September 2011 beurteilte die Politische Gemeinde Frauenfeld die Anträge der Eheleute A._ als baupolizeiliche Anzeige und stellte fest, dass keine Massnahmen zur Wiederherstellung des gesetzmässigen Zustandes erforderlich seien. Sie hielt im Wesentlichen fest, dass eine Massüberschreitung um wenige Zentimeter im Bereich der üblicherweise und bei Bauvorhaben stets hinzunehmenden Toleranz liege. Ein Rückbau wäre zudem unverhältnismässig, da weder öffentliche noch private Interessen vorlägen, die eine Änderung am Sitzplatz erforderten. Auf den Antrag bezüglich Anpassung des Grundbucheintrages trat die Politische Gemeinde Frauenfeld nicht ein. C. A.A._ und B.A._ erhoben dagegen Rekurs beim Departement für Bau und Umwelt des Kantons Thurgau. Dieses hiess den Rekurs mit Entscheid vom 31. Mai 2012 bezüglich der Höhe der erstinstanzlichen Gebühren gut, wies ihn hingegen im Übrigen ab, soweit es darauf eintrat. Die Eheleute A._ erhoben gegen diesen Entscheid Beschwerde beim Verwaltungsgericht des Kantons Thurgau. Mit Urteil vom 14. November 2012 wies das Verwaltungsgericht die Beschwerde ab, soweit es darauf eintrat. D. A.A._ und B.A._ führen Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht mit vielzähligen Rechtsbegehren. Hauptsächlich stellen sie den Antrag, das Hochbauamt der Stadt Frauenfeld müsse seine baupolizeilichen Aufgaben wahrnehmen und eine Verfügung erlassen, um die Baute entsprechend dem unterschriebenen Bauprojekt mit den darin aufgeführten Massen (Höhe der Mauer 60 cm, Höhe des Podestes 50 cm ab der im unterschriebenen Bauprojekt eingezeichneten Nulllinie) zurückbauen zu lassen. Weiter beantragten sie die "rechtliche Anerkennung der mündlich privatrechtlichen Vereinbarung, datiert vom 19. Oktober 2008, der Familien C._ und A._ durch das Hochbauamt der Stadt Frauenfeld bei zukünftigen Bauvorhaben auf dem Grundstück der Familie C._ mit Parzellennummer cccc Und/oder in Aberkennung vom Hochbauamt respektive Stadtrat unserer berechtigten Forderung bezüglich: dass jede Beschattungsanlage keinen Schatten auf das Grundstück der Familie A._ (aaaa) werfen darf, ist die Unterschrift zum Näherbaurecht als nichtig zu betrachten". Dabei sei abzuklären, ob privatrechtlich von den öffentlichrechtlichen Bestimmungen zu den Grenzabständen abgewichen werden dürfe und dies von den zuständigen Behörden berücksichtigt werden müsse. Eventuell sei abzuklären, ob das Hochbauamt der Stadt Frauenfeld eine Reduktion des gesetzlichen Grenzabstandes (von drei Metern auf zwei Meter) bei einer Baueingabe für eine Beschattungsanlage auf der Parzelle cccc akzeptieren durfte. Zur Begründung rügen die Eheleute A._ sinngemäss eine Verletzung des Rechtsgleichheitsgebotes (Art. 8 BV), des Willkürverbotes (Art. 9 BV) sowie des Verhältnismässigkeitsprinzips (Art. 5 Abs. 2 BV). E. Das Verwaltungsgericht des Kantons Thurgau beantragt, die Beschwerde vollumfänglich abzuweisen. Die Politische Gemeinde Frauenfeld und das Departement für Bau und Umwelt des Kantons Thurgau beantragen die Abweisung der Beschwerde, soweit darauf einzutreten sei. C.C._ äusserte sich in seiner Vernehmlassung zur Sache ohne einen ausdrücklichen Antrag zu stellen. F. Die Eheleute A._ halten in ihrer Replik an ihren Anträgen fest. 