Sachverhalt:
A.
A.a. A.A._ und B.A._ (Mieter, Beschwerdeführer) mieten seit dem 1. Juli 1998 eine 4.5-Zimmerwohnung in V._, Strasse W._. Mit amtlich genehmigtem Formular wurde ihnen am 8. März 2002 durch die damalige Vermieterin folgende Mietvertragsänderung mitgeteilt:
"A. Für Mietzinsänderung Bisher: Neu:
1. Mietzins ohne Nebenkosten Fr. 1'935.00 Fr. 1'811.00
2. Nebenkosten
Heizungskosten akonto Fr. 80.00 Fr. 80.00
Betriebskosten akonto Fr. 0.00 Fr. 179.00
Strom Fr. 10.00 Fr. 0.00
Antennen- u. Urheberrechtsgeb. Fr. 45.00 Fr. 0.00
Total pro Monat Fr. 2'070.00 Fr. 2'070.00
Klare Begründung: Anpassung in Fr.
Senkung der Nettomiete im Umfang
der neu ausgeschiedenen Betriebskosten Fr. 124.00-
Einführung Akontozahlungen für Betriebskosten Fr. 179.00
Einschluss Strompauschale für die Betriebskosten Fr. 10.00-
Einschluss TV-Pauschale in die Betriebskosten Fr. 45.00-
B. Für andere einseitige Vertragsänderungen
Umschreibung und klare Begründung:
Erhebung neuer bisher im Nettomietzins inbegriffener Betriebskosten nach separater Abrechnung gem. sep. Beilage mit den genauen Details. Die Senkung der Nettomiete entspricht dem bisherigen Umfang der neu ausgeschiedenen Betriebskosten. Begründung: Schaffung einer grösseren Kostentransparenz.
Wir machen Sie darauf aufmerksam, dass die Mietzinsänderung, bzw. andere einseitige Vertragsänderung, innert 30 Tagen seit dem Empfang der Mitteilung bei der Paritätischen Schlichtungsbehörde des Bezirks, in dem sich das Mietobjekt befindet (zuständiges Bezirksgericht), als missbräuchlich angefochten werden kann."
Als Beilage erhielten die Mieter ein Schreiben mit folgendem Wortlaut:
"Auslagerung der Betriebskosten aus dem Nettomietzins
Sehr geehrte Mieterin, sehr geehrter Mieter
Um eine bessere Kostentransparenz zu schaffen werden auf den 01.07.02 die unten aufgeführten Betriebskosten, die bisher im Nettomietzins enthalten waren, separat ausgeschieden und zusammen mit den Heizkosten periodisch abgerechnet. Allfällige bisherige Pauschalen werden ebenfalls in die Heiz- oder in die Betriebskostenabrechnung integriert.
Dem amtlichen Mietzinsanpassungsformular können Sie den neu einge führten Akontobetrag für die Betriebskosten entnehmen. Der bisherige Nettomietzins wurde um den entsprechenden Betrag reduziert, so dass sich der Bruttomietzins effektiv nicht verändert.
Für die Berechnung der Nettomietzinssenkung und der Betriebskosten- Akontozahlung wurden die Kosten für die unten aufgeführten Positionen der entsprechenden Vorjahresperiode berechnet und anschliessend auf jedes Objekt verteilt.
Es werden inskünftig folgende Betriebskosten separat abgerechnet:
- Hauswartung inkl. Verbrauchsmaterial
- Allgemeinstrom
- Wasserverbrauch, Abwasser, Meteorwasser, Kanalreinigung
- Kehrichtabfuhr, Containerreinigung
- Kabelfernseh- und -radiogebühren inkl. Urheberrechtsgebühr
- Pflege von Garten, Umgebung und Pflanzentrögen
- Serviceabonnemente für Lift, (da vorhanden) Maschinen, Geräte und
Anlagen
Für die Abrechnung werden zusätzlich 4 % Verwaltungskosten zuzüglich MWSt. berechnet.
Für Fragen kontaktieren Sie bitte Ihren Verwalter."
A.b. Am 20. Dezember 2013 kaufte die C._ Anlagestiftung (Vermieterin, Beschwerdegegnerin) die Liegenschaft, in welcher sich das Mietobjekt befindet. Aufgrund von <ref-law> ging das Mietverhältnis in diesem Zeitpunkt von Gesetzes wegen auf die C._ Anlagestiftung über.
B.
B.a. Am 13. Juni 2018 erhoben die Mieter beim Mietgericht Meilen Klage, worin sie beantragten, die Mietzinsänderung vom 2. Juli 2002 (recte: vom 8. März 2002 mit Wirkung per 1. Juli 2002) sei für nichtig zu erklären. Überdies sei festzustellen, dass die Neueinführung der Betriebskosten nicht gültig vereinbart worden sei und lediglich die Heizkosten, die Stromkostenpauschale sowie die TV-Pauschale gelte. Ferner begehrten sie die Rückerstattung bezahlter Nebenkosten im Umfang von Fr. 7'168.40 zuzüglich Zins. Eventualiter sei die Vermieterin zu verpflichten, den Mietern korrekte Nebenkostenabrechnungen ab 2007/08 bis 2015/16 zukommen zu lassen.
Das Mietgericht wies die Klage ab, soweit es darauf eintrat. Es erwog, die Mietvertragsänderung habe sämtlichen Anforderungen an eine ausreichende Begründung entsprochen. Auf eine indirekte Mietzinserhöhung gebe es keine Hinweise. Ein Anspruch auf Rückerstattung bestehe mangels Nichtigkeit der Mietvertragsänderung nicht.
B.b. Gegen diesen Entscheid erhoben die Mieter beim Obergericht des Kantons Zürich mit Eingabe vom 6. April 2020 Berufung. Sie beantragten, das Urteil des Mietgerichts sei aufzuheben und ihre bereits vor der Erstinstanz gestellten Rechtsbegehren seien gutzuheissen. Eventualiter seien die Akten in Gutheissung der Berufung zur neuen Entscheidung mit der Weisung zur Durchführung eines Beweisverfahrens an die Erstinstanz zurückzuweisen.
Mit Urteil vom 20. Mai 2020 wies das Obergericht die Berufung ab, soweit es darauf eintrat. Es begründete seinen Entscheid damit, dass die Mietvertragsänderung ausreichend klar begründet gewesen sei. Mangels Nichtigkeit der Vertragsänderung stehe den Mietern weder ein Rückforderungsanspruch noch ein Anspruch auf Erstellung neuer Nebenkostenabrechnungen zu. Auf das Feststellungsbegehren sei mangels schutzwürdigen Interesses nicht einzutreten. Aus der Prüfung der Nichtigkeit der Mietzinsänderung ergebe sich automatisch, welche Nebenkostenpositionen gälten: entweder diejenigen, die vor der Änderung bestanden hätten, oder diejenigen, die mit der Mietzinsänderung eingeführt worden seien.
C.
Mit Beschwerde in Zivilsachen, eventualiter subsidiärer Verfassungsbeschwerde, vom 2. Juli 2020 beantragen die Beschwerdeführer, den Entscheid des Obergerichts des Kantons Zürich kostenfällig aufzuheben und die vor der Vorinstanz gestellten Anträge gutzuheissen. Eventualiter sei die Sache zur Durchführung eines Beweisverfahrens an die Erstinstanz, subeventualiter an die Vorinstanz, zurückzuweisen.
Die Beschwerdegegnerin beantragt unter Kostenfolgen, auf die Beschwerde nicht einzutreten, eventualiter diese abzuweisen. Die subsidiäre Verfassungsbeschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Die Parteien replizierten bzw. duplizierten unaufgefordert. Die Beschwerdeführer reichten - ebenfalls unaufgefordert - eine Triplik ein. Die Vorinstanz verzichtete auf Vernehmlassung.

Erwägungen:
1.
1.1. Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-law>; <ref-ruling> E. 2.1 S. 397).
1.2. Nach <ref-law> beträgt die Streitwertgrenze für vermögensrechtliche Angelegenheiten mietrechtlicher Natur Fr. 15'000.--. Der angefochtene Entscheid stellt einen Endentscheid dar. Bei diesen bestimmt sich der Streitwert nach den Begehren, die vor der Vorinstanz streitig geblieben waren (<ref-law>). Dies betrifft sämtliche vorinstanzlich gestellten Rechtsbegehren.
1.2.1. Die Vorinstanz bezifferte den Streitwert mit der Erstinstanz in Anwendung von <ref-law> (Streitwert nach Rechtsbegehren unter Ausschluss von Zinsen und Verfahrenskosten) auf je Fr. 7'168.40 pro Rechtsbegehren, insgesamt ausmachend Fr. 21'505.20. Die Beschwerdeführer beziffern den Streitwert vor Bundesgericht auf ebendiesen Betrag. Die Beschwerdegegnerin bestreitet diesen Wert. Sie führt aus, die vor der Vorinstanz strittig gebliebenen Rechtsbegehren würden einander ausschliessen, weshalb der Streitwert bloss Fr. 7'168.40 betrage.
1.2.2. Nach <ref-law> werden mehrere in einer vermögensrechtlichen Sache von der gleichen Partei geltend gemachte Begehren zusammengerechnet, sofern sie sich nicht gegenseitig ausschliessen. Dies trifft dann zu, wenn die Gutheissung des einen Begehrens zwingend zur Abweisung des anderen führt oder wenn die Begehren ineinander aufgehen.
1.2.2.1. Die Beschwerdeführer stellten vor der Vorinstanz erstens das Begehren um Nichtigerklärung der Mietzinsänderung vom 8. März 2002; zweitens verlangten sie die Feststellung, dass die Neueinführung der Betriebskosten von Fr. 179.-- nicht gültig vereinbart worden sei und lediglich die Heizkosten von monatlich Fr. 80.-- akonto, die Stromkostenpauschale von Fr. 10.-- sowie die pauschalen Antennengebühren von Fr. 45.-- gelten sollen und drittens, forderten sie von der Beschwerdegegnerin die Rückerstattung von Fr. 7'168.40 zuzüglich Zins wegen angeblich zu viel bezahlter Nebenkosten. Vorliegend ist nicht ersichtlich, dass die Gutheissung eines dieser drei Rechtsbegehren zwingend zur Abweisung eines anderen führte.
Fraglich ist indessen, ob sie ineinander aufgehen: Indem die Beschwerdeführer mit ihrem zweiten Rechtsbegehren die Feststellung verlangen, die Neueinführung der Betriebskosten sei nicht gültig vereinbart worden, begehren sie nichts anderes als die Feststellung der Nichtigkeit dieser, was sich mit dem ersten Rechtsbegehren deckt. Daran ändert auch der Zusatz nichts, wonach die von ihnen genannten Beträge als Nebenkosten zu bestätigen seien. Mithin gehen das erste und das zweite Rechtsbegehren ineinander auf, weshalb sie bei der Streitwertberechnung nicht zu addieren sind.
1.2.2.2. Gegenteiliges gilt für das dritte Rechtsbegehren: Der Streitwert des ersten und des zweiten Rechtsbegehrens berechnet sich nach <ref-law>, demzufolge als Wert wiederkehrender Leistungen der Kapitalwert gilt. Dieser Kapitalwert deckt die Zeit von der Klageerhebung in die Zukunft ab, sofern das Mietverhältnis - wie vorliegend - weiterbesteht. Verlangt der Mieter überdies die Rückerstattung zu viel bezahlter Beträge für die Vergangenheit, wird damit eine andere Zeitspanne visiert, weshalb der Wert dieses Begehrens dem Interessenwert der wiederkehrenden Leistung für die Zukunft hinzuzuzählen ist.
Bei ungewisser oder unbeschränkter Dauer gilt als Kapitalwert der zwanzigfache Betrag der einjährigen Nutzung oder Leistung (<ref-law>). Gemäss dem Schreiben vom 8. März 2002 sollten ab dem 1. Juli 2002 bisher pauschal erhobene Betriebskosten von Fr. 124.-- aus dem Nettomietzins ausgegliedert und nunmehr akonto abgerechnet werden. Der monatliche Bruttomietzins wurde bei Fr. 2'070.-- belassen. Eine Kapitalisierung im Umfang der ausgeschiedenen Betriebskosten würde in einem Streitwert von Fr. 29'760.-- (Fr. 124.-- x 12 Monate x 20 Jahre) resultieren, was indes den tatsächlichen Gegebenheiten widerspräche, hätten doch die Beschwerdeführer diese Fr. 124.-- auch dann zu entrichten, wenn die Mietvertragsänderung nichtig wäre. Vorliegend ist der Kapitalisierungswert aus der Differenz zwischen den tatsächlich bezahlten Betriebskosten und dem Betrag der Ausgliederung (Fr. 124.--) zu errechnen. Da diese Differenz jedes Jahr unterschiedlich ausfiel, wäre es sachfremd, lediglich auf einen Nachzahlungsbetrag abzustellen. Vielmehr erscheint es sachgerecht, aus den von den Beschwerdeführern behaupteten jährlichen Nachzahlungen einen Durchschnitt zu bilden und diesen als Kapitalisierungswert zu verwenden. Die Vorinstanz stellte mit Verweis auf die Erstinstanz fest, es sei unbestritten, dass bis zur Abrechnung 2007/08 keine Nachzahlungen hätten geleistet werden müssen. In ihrer Klageschrift an die Erstinstanz präsentierten die Beschwerdeführer die Beträge der Nachzahlungen von 2007/08 bis 2015/16. Selbst wenn man zulasten der Beschwerdeführer davon ausgeht, dass die vorerwähnte Feststellung der Vorinstanz zutrifft (was die Beschwerdeführer jedoch bestreiten), mithin zur Ermittlung des Durchschnitts für die Perioden 2002/03 bis und mit 2006/07 jeweils ein Wert von Fr. 0.- eingesetzt wird, beläuft sich der Streitwert des ersten bzw. des zweiten Rechtsbegehrens auf über Fr. 8'400.-- (durchschnittliche Nachzahlungen von 2002/03 bis 2015/16 von abgerundet Fr. 35.--/Monat bzw. Fr. 420.--/Jahr x 20 Jahre). Addiert man dazu den Streitwert des dritten Rechtsbegehrens von Fr. 7'168.40, überschreitet der Gesamtstreitwert die Streitwertgrenze von Fr. 15'000.--. Mithin ist die Beschwerde in Zivilsachen zulässig.
1.3. Die übrigen Eintretensvoraussetzungen geben keinen Anlass zu Bemerkungen. Auf die Beschwerde ist - unter Vorbehalt einer genügenden Begründung (Art. 42 Abs. 1 und 2 BGG) - einzutreten. Folglich ist auf die subsidiäre Verfassungsbeschwerde nicht einzutreten (vgl. <ref-law>).
2.
2.1. Mit Beschwerde in Zivilsachen können Rechtsverletzungen nach Art. 95 und 96 BGG gerügt werden. Die Beschwerde ist hinreichend zu begründen, ansonsten darauf nicht eingetreten werden kann (<ref-ruling> E. 2 S. 116; <ref-ruling> E. 2.1 S. 245 f.). In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Unerlässlich ist dabei, dass auf die Begründung des angefochtenen Entscheids eingegangen und im Einzelnen aufgezeigt wird, worin eine vom Bundesgericht überprüfbare Rechtsverletzung liegt. Die beschwerdeführende Partei soll in der Beschwerde an das Bundesgericht nicht bloss die Rechtsstandpunkte, die sie im kantonalen Verfahren eingenommen hat, erneut bekräftigen, sondern mit ihrer Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (<ref-ruling> E. 2 S. 116, 86 E. 2 S. 89).
2.2.
2.2.1. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Dazu gehören sowohl die Feststellungen über den streitgegenständlichen Lebenssachverhalt als auch jene über den Ablauf des vor- und erstinstanzlichen Verfahrens, also die Feststellungen über den Prozesssachverhalt (<ref-ruling> E. 1.3.1 S. 17 f. mit Hinweisen). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 2 S. 117, 264 E. 2.3 S. 266). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein können (<ref-law>).
Für eine Kritik am festgestellten Sachverhalt gilt das strenge Rügeprinzip von <ref-law> (<ref-ruling> E. 2.3 S. 266 mit Hinweisen). Die Partei, welche die Sachverhaltsfeststellung der Vorinstanz anfechten will, muss klar und substanziiert aufzeigen, inwiefern diese Voraussetzungen erfüllt sein sollen (<ref-ruling> E. 1.3.1 S. 18 mit Hinweisen). Wenn sie den Sachverhalt ergänzen will, hat sie zudem mit präzisen Aktenhinweisen darzulegen, dass sie entsprechende rechtsrelevante Tatsachen und taugliche Beweismittel bereits bei den Vorinstanzen prozesskonform eingebracht hat (<ref-ruling> E. 2 S. 90). Genügt die Kritik diesen Anforderungen nicht, können Vorbringen mit Bezug auf einen Sachverhalt, der vom angefochtenen Entscheid abweicht, nicht berücksichtigt werden (<ref-ruling> E. 1.3.1 S. 18).
2.2.2. Diese Grundsätze verkennen die Beschwerdeführer, wenn sie in ihrer Beschwerdeschrift an das Bundesgericht den Sachverhalt eingehend aus ihrer Sicht schildern, ohne substanziierte Rügen vorzutragen. Die entsprechenden Ausführungen haben unbeachtet zu bleiben. Massgebend bleibt der von der Vorinstanz festgestellte Sachverhalt.
2.3. Beruht ein Entscheid auf mehreren selbständigen alternativen Begründungen, ist für jede einzelne darzutun, weshalb sie Recht verletzt, denn soweit nicht beanstandete Begründungen das angefochtene Urteil selbständig stützen, fehlt das Rechtsschutzinteresse an der Beurteilung der gehörig begründeten Rügen (<ref-ruling> E. 6.3 S. 120 f.; vgl. auch <ref-ruling> E. 3.2 S. 560; je mit Hinweisen).
3.
Soweit die Beschwerdeführer unter Verweis auf die Erwägung 1.1 der Vorinstanz festhalten, diese impliziere, sie hätten erkennen müssen, dass die bisherige Zusammensetzung des Mietzinses mit der neuen Zusammensetzung in der Formularanzeige gegenübergestellt worden sei und die Senkung des Nettomietzinses dem bisherigen Umfang der neu ausgeschiedenen Betriebskosten entspreche, ist ihnen nicht zu folgen, gibt die Vorinstanz doch in der fraglichen Erwägung bloss den Inhalt des Mietvertragsänderungsformulars und des Begleitschreibens wieder, ohne daraus Schlüsse irgendwelcher Art zu ziehen. Insofern ist die auf diese irrige Feststellung abgestützte Rüge, wonach die Vorinstanz ohne Belege davon ausgegangen sei, dass der Betrag, in welchem der Nettomietzins gesenkt worden sei, Fr. 124.--, den neu ausgeschiedenen Betriebskosten entspreche, unbegründet.
4.
Wenn die Beschwerdeführer weiter rügen, die Vorinstanz habe mit ihrer Erwägung 1.4 diverse Rechtsverletzungen begangen, da sie die Argumente der Beschwerdeführer nicht geprüft habe und die einzelnen Rügen als pauschale Kritik an den erstinstanzlichen Erwägungen abtue, ist ihnen ebenfalls nicht zu folgen. Die Vorinstanz beschränkte sich in der erwähnten Erwägung lediglich darauf, die anwendbaren Verfahrensbestimmungen darzulegen, ohne jedoch daraus einen Schluss auf den zu beurteilenden Sachverhalt zu ziehen. Inwiefern darin eine Rechtsverletzung bestehen sollte, legen die Beschwerdeführer nicht dar, weshalb sie den Rügeanforderungen nicht genügen (vgl. E. 2.1 hiervor).
5.
Die Beschwerdeführer rügen eine Verletzung des rechtlichen Gehörs, da ihnen die Erstinstanz das Protokoll der Hauptverhandlung nicht zur Stellungnahme habe zukommen lassen und die Vorinstanz dieses Vorgehen geschützt habe.
5.1. Gemäss <ref-law> steht den Parteien das rechtliche Gehör zu. Es dient einerseits der Klärung des Sachverhaltes, anderseits stellt es ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheids dar, welcher in die Rechtsstellung des Einzelnen eingreift. Dazu gehört insbesondere das Recht der betroffenen Person, sich vor Erlass eines sie belastenden Entscheids zur Sache, jedenfalls zumindest zum Beweisergebnis äussern zu können, wenn dieses geeignet ist, den Ausgang des Verfahrens zu beeinflussen. Dieser Anspruch ist formeller Natur, womit seine Verletzung grundsätzlich ungeachtet der materiellen Begründetheit des Rechtsmittels zur Gutheissung der Beschwerde und zur Aufhebung des angefochtenen Entscheids führt (<ref-ruling> E. 2.2 E. S. 190 mit Hinweisen). Nach der Rechtsprechung kann eine - nicht besonders schwerwiegende - Verletzung des rechtlichen Gehörs ausnahmsweise als geheilt gelten, wenn die betroffene Person die Möglichkeit erhält, sich vor einer Beschwerdeinstanz zu äussern, die sowohl den Sachverhalt wie die Rechtslage frei überprüfen kann (<ref-ruling> E. 3d/aa S. 437). Von einer Rückweisung der Sache ist selbst bei einer schwerwiegenden Verletzung des rechtlichen Gehörs dann abzusehen, wenn und soweit die Rückweisung zu einem formalistischen Leerlauf und damit zu unnötigen Verzögerungen führen würde, die mit dem (der Anhörung gleichgestellten) Interesse der betroffenen Partei an einer beförderlichen Beurteilung der Sache nicht zu vereinbaren wären (<ref-ruling> E. 2.2 S. 204 f., 132 V 387 E. 5.1 S. 390 mit Hinweis, vgl. auch <ref-ruling> E. 4 S. 396 ff.).
5.2. Die Vorinstanz hielt hierzu fest, dass sowohl im ordentlichen als auch im vereinfachten Verfahren aufgrund von <ref-law> ein Anspruch der Parteien bestehe, sich abschliessend zum Beweisergebnis und zu den Rechtsfragen äussern zu können. Indes gebe es schriftliche anstatt mündliche Schlussvorträge nur auf entsprechenden gemeinsamen Antrag der Parteien, was sich aus <ref-law> ergebe. Vorliegend mangle es an einem solchen. Überdies hätten die Beschwerdeführer in ihrer Berufung nicht dargelegt, welche Vorbringen sie in einer Stellungnahme zum Protokoll der Hauptverhandlung in das erstinstanzliche Verfahren eingeführt hätten und inwiefern diese hätten erheblich sein können, was jedoch für eine erfolgreiche Geltendmachung einer Gehörsverletzung gemäss bundesgerichtlicher Rechtsprechung (vgl. Urteil 5A_561/2018 vom 14. Dezember 2018 E. 2.3) vorausgesetzt sei.
5.3. Die Beschwerdeführer bringen hierzu vor, sie hätten zu keiner Zeit, weder mündlich noch konkludent, auf die mündlichen Schlussvorträge verzichtet. Wenn die Erstinstanz auf eine Schlussverhandlung hätte verzichten wollen, so hätte sie von den Parteien eine entsprechende Erklärung einholen müssen. Eine Heilung dieser Gehörsverletzung wäre möglich gewesen, wenn die Vorinstanz den erstinstanzlichen Entscheid sowohl tatsächlich wie rechtlich frei überprüft hätte, was sie indes nicht getan habe. So sei diese auf die Stellungnahmen in der Berufung nicht eingegangen und habe zu Unrecht die Ausführungen und Belege als unzulässige Noven nicht berücksichtigt.
5.4. Damit übersehen die Beschwerdeführer, dass die Vorinstanz ihre Entscheidung in diesem Punkt doppelt begründete (1. fehlender Antrag der Parteien, schriftliche Schlussvorträge einzureichen; 2. fehlende Angabe der Vorbringen, welche in die Stellungnahme Eingang gefunden hätten sowie deren Relevanz für die Entscheidung). Da die Beschwerdeführer sich zur letzteren Begründung nicht äussern, ist auf ihre Rüge nicht einzutreten (vgl. E. 2.3 hiervor).
6.
Die Beschwerdeführer wenden ein, die Vorinstanz sei zu Unrecht nicht auf ihr Feststellungsbegehren eingetreten, dass die Neueinführung der Betriebskosten nicht gültig vereinbart worden sei und lediglich die Heizkosten, die Stromkostenpauschale sowie die TV-Pauschale gälten.
6.1. Die Vorinstanz hielt fest, die Erstinstanz habe zu Recht erwogen, aus der Prüfung der Nichtigkeit der Mietzinsänderung vom 8. März 2002 ergebe sich automatisch, welche Nebenkostenpositionen gelten würden, nämlich entweder diejenigen, die vor der Änderung bestanden hätten, oder diejenigen, welche mit der Mietzinsänderung eingeführt worden seien. Mangels schutzwürdigen Interesses sei die Erstinstanz zutreffenderweise nicht auf das Rechtsbegehren eingetreten.
6.2. Die Beschwerdeführer wenden ein, obgleich normalerweise kein Feststellungsinteresse bestehe wenn eine Gestaltungs- oder eine Leistungsklage möglich sei, hätten sie aufgrund der jeweils ändernden Pauschale und der unklaren Nebenkostenregelung sehr wohl ein Interesse daran, zu klären, welche Nebenkosten nebst den Heizkosten zukünftig geschuldet seien. Sie seien verunsichert, was zukünftig gelte.
6.3. Es ist nicht ersichtlich, inwiefern diese angebliche Unsicherheit nicht durch die Gutheissung oder Abweisung des ersten Rechtsbegehrens der Beschwerdeführer (Nichtigerklärung der Mietzinsänderung vom 8. März 2002) beseitigt würde. Wie die Vorinstanz zutreffend ausführte, ergibt sich daraus ohne Weiteres, welche Nebenkosten geschuldet sind. Folglich ist die Vorinstanz zu Recht nicht auf das Feststellungsbegehren eingetreten.
7.
Die Beschwerdeführer rügen weiter, die Vorinstanz habe zu Unrecht die Gültigkeit der Mietzinsänderung bejaht.
7.1. Gemäss <ref-law> sind Mietzinserhöhungen nichtig, wenn der Vermieter sie nicht mit dem vorgeschriebenen Formular mitteilt, sie nicht begründet oder mit der Mitteilung die Kündigung androht oder ausspricht. Dies gilt nach <ref-law> auch, wenn der Vermieter beabsichtigt, "sonstwie den Mietvertrag einseitig zu Lasten des Mieters zu ändern, namentlich seine bisherigen Leistungen zu vermindern oder neue Nebenkosten einzuführen". Der Geltungsbereich von <ref-law> ist nicht von vornherein auf vertragliche Änderungen beschränkt, welche das bisherige Gleichgewicht der Leistungen zu Lasten des Mieters verändern. Ob sich die Änderung zu Lasten des Mieters auswirkt, ist vielmehr Ergebnis der Beurteilung im Anfechtungsverfahren und gehört zur materiellen Missbrauchsprüfung (<ref-ruling> E. 3b S. 235).
Nach Art. 19 Abs. 1 lit. b und c der Verordnung vom 9. Mai 1990 über die Miete und Pacht von Wohn- und Geschäftsräumen (VMWG; SR 221.213.11) muss das Formular für die Mitteilung von anderen einseitigen Vertragsänderungen im Sinne von <ref-law> (i) die Umschreibung der Forderung, (ii) den Zeitpunkt, auf den die Vertragsänderung wirksam wird, (iii) die klare Begründung dieser Forderung, (iv) die gesetzlichen Voraussetzungen der Anfechtung der Vertragsänderung sowie (v) das Verzeichnis der Schlichtungsbehörden und ihre örtliche Zuständigkeit enthalten. Falls die Begründung in einem Begleitschreiben erfolgt, hat der Vermieter im Formular ausdrücklich darauf hinzuweisen (<ref-law>). Die Begründung ist "klar" im Sinne von <ref-law>, wenn sie dem Mieter erlaubt, sich ein Bild über Tragweite und Berechtigung der Änderung zu machen und ihm damit die Entscheidungsgrundlagen dafür verschafft, ob er Einsprache erheben will oder nicht (<ref-ruling> E. 3.2.1 S. 365; <ref-ruling> E. 3a S. 8; Urteile 4A_571/2017 vom 10. Juli 2018 E. 4.1.1.2; 4A_268/2011 vom 6. Juli 2011 E. 3.2.1; 4A_409/2009 vom 1. Februar 2010 E. 2.1). Die Begründung ist ungenügend, wenn sie nicht angibt, welchen bis anhin im Mietzins enthaltenen Aufwendungen die künftig gesondert in Rechnung gestellten Kosten entsprechen. Der Mieter kann sich von der Tragweite der Änderung nur dann ein Bild machen, wenn er die Beträge kennt, die der Vermieter früher für die Kosten aufgewendet hat, die nun gesondert erhoben werden sollen. Das Erfordernis der Klarheit bedeutet nicht nur, dass im Einzelnen anzugeben ist, welche Nebenkosten dem Mieter künftig direkt in Rechnung gestellt werden sollen, sondern dass auch ersichtlich sein muss, wie sich die Aussonderung der Kosten auf das Mietzinsgefüge auswirkt. Der Mieter muss demnach in der Lage sein zu entscheiden, ob die Höhe der neuen Akontozahlung den tatsächlichen Aufwendungen entspricht, beziehungsweise ob der Mietzins ansteigen wird (zum Ganzen <ref-ruling> E. 3.2.1 S. 365; <ref-ruling> E. 4b S. 466 f.). Unzureichend ist namentlich der Verweis des Mieters auf die Einsichtnahme in die internen Berechnungsgrundlagen, da damit der Sinn der Begründungspflicht verkannt würde (Urteil 4C.137/1999 vom 23. August 1999 E. 2c, in: MietRecht Aktuell [MRA] 2000 S. 301). Gemäss bundesgerichtlicher Rechtsprechung ist die Vertragsänderung nicht nur dann nichtig, wenn der Vermieter sie (überhaupt) nicht begründet (vgl. <ref-law>), sondern auch dann, wenn diese Begründung nicht hinreichend klar ist (<ref-ruling> E. 3.3 S. 377; <ref-ruling> E. 3.2.1 S. 365 f.; <ref-ruling> E. 3b S. 8 f., 460 E. 4a/cc S. 466 zit. Urteil 4A_268/2011 E. 3.2.1). Ausreichend klar ist die Begründung dann, wenn sich der Mieter als vernünftiger und korrekter Vertragspartner unter Berücksichtigung aller massgebenden Umstände im Zeitpunkt des Zugangs der Erklärung Klarheit darüber verschaffen kann, auf welchen Erhöhungsgrund sich der Vermieter beruft (<ref-ruling> E. 3.3 S. 377).
Genügt der Vermieter den Begründungsanforderungen von <ref-law> - ist mithin die Mietzinserhöhung oder die anderweitige einseitige, zu Lasten des Mieters ausfallende, Mietvertragsänderung nicht nichtig -, steht dem Mieter trotzdem die Möglichkeit offen, gegen diese vorzugehen, sofern sie missbräuchlich im Sinne von Art. 269 f. OR ist (<ref-law>). Mietzinse sind missbräuchlich, wenn damit ein übersetzter Ertrag aus der Mietsache erzielt wird oder wenn sie auf einem offensichtlich übersetzten Kaufpreis beruhen (<ref-law>). Dies trifft in der Regel nicht zu, wenn eine in <ref-law> aufgezählte Konstellation vorliegt.
7.2. Soweit die Beschwerdeführer unter den Ziffern 3.1 und 3.2 der Beschwerdeschrift die vorinstanzlichen Ausführungen in deren Erwägung 3.1 und 3.2 beanstanden, übersehen sie, dass die Vorinstanz dort lediglich die Position der Beschwerdeführer im Verfahren vor der Erstinstanz, die rechtliche Beurteilung der Erstinstanz sowie die Vorbringen der Beschwerdeführer im Berufungsverfahren zusammenfasste. Es handelt sich hierbei nicht um eine eigene rechtliche Würdigung der Vorinstanz. Was die Beschwerdeführer hier rügen könnten, wäre eine willkürliche Feststellung des Prozesssachverhalts durch die Vorinstanz (vgl. E. 2.2.1 hiervor). Dazu hätten sie sich allerdings auf konkrete Stellen in ihren Rechtsschriften bzw. in der erstinstanzlichen Urteilsbegründung berufen und diese der vorinstanzlichen Zusammenfassung gegenüberstellen müssen. Da sie dies nicht getan haben, ist auf ihre Ausführungen unter den Ziffern 3.1 und 3.2 nicht einzutreten.
7.3. Auch ihre in Ziff. 3.3 geäusserte Kritik an der Erwägung 3.3 geht an der Sache vorbei. Die Vorinstanz gibt darin bloss die Erwägung 3.2.1 von <ref-ruling> in extenso vom Französischen ins Deutsche übersetzt wieder und hält mit Verweis auf die dortige Erwägung 3.3 fest, das Bundesgericht erachte den Formulierungsvorschlag für die Änderung des Mietzinses aus dem SVIT-Kommentar (RAYMOND BISANG UND ANDERE, Das schweizerische Mietrecht, 3. Aufl. 2008, N. 68 zu <ref-law>) als hinreichend, da es unter anderem auf diesen verweise. Daraus ist indes nicht ersichtlich, dass die Vorinstanz - wie von den Beschwerdeführern moniert - in willkürlicher Weise davon ausgegangen wäre, dass die Beschwerdeführer als Laien die Kostenstruktur kennen müssten, weshalb sie sich ein Bild über die Tragweite und Berechtigung der Vertragsänderung hätten machen können. Ebenfalls nicht zu folgen ist den Beschwerdeführern wenn sie behaupten, die Vorinstanz impliziere dadurch, die Verwaltung habe den Formulierungsvorschlag dem SVIT-Kommentar aus dem Jahr 2008 entnommen. Es ist nicht nachvollziehbar, woran die Beschwerdeführer eine derartige Implikation festmachen, ist doch offensichtlich, und durfte deshalb der Vorinstanz nicht verborgen geblieben sein, dass die Beschwerdegegnerin auf ihrem Formular aus dem Jahr 2002 keinen Formulierungsvorschlag aus einem sechs Jahre später erscheinenden Werk verwendet haben konnte.
7.4. Die Beschwerdeführer erachten die Mietvertragsänderung als nicht hinreichend begründet, weshalb <ref-law> verletzt werde.
7.4.1. Die Vorinstanz erwog, vorliegend beinhalte das den Beschwerdeführern zugestellte Formular betreffend die Mietzinsänderung samt Begleitschreiben sämtliche Angaben des vom Bundesgericht als genügend erachteten Formulierungsvorschlags aus dem SVIT-Kommentar (siehe E. 7.3 hiervor). Daraus sei insbesondere ersichtlich, welche bisher im Nettomietzins enthaltenen Positionen ausgeschieden würden, welche Kosten diese Positionen bisher gesamthaft verursacht hätten und wie sich die Aussonderung der Kosten auf das Mietzinsgefüge auswirke. Aus der Begründung ergebe sich schliesslich auch, weshalb die Änderung erfolge. Entgegen der Ansicht der Beschwerdeführer verlange insbesondere der vom Bundesgericht als genügend erachtete Formulierungsvorschlag aus dem SVIT-Kommentar nicht zwingend, dass in einem separaten Schreiben eine konkrete rechnerische Aufstellung der einzelnen Nebenkosten aufgeführt werde. Die Verteilschlüssel müssten erst in der auf die Änderung folgenden Nebenkostenabrechnung angegeben werden. Überdies seien die Kosten der ausgeschiedenen Positionen nicht zwingend auf einem Durchschnitt mehrerer Vorjahresperioden zu errechnen. Zwar blieben durch das blosse Abstellen auf den Aufwand des Vorjahrs starke Schwankungen unberücksichtigt, doch würde andererseits bei Kalkulation mit einem Durchschnittswert über mehrere Jahre in Kauf genommen, dass - bedingt durch eine allfällige inflationäre Entwicklung der einzelnen Nebenkostenpositionen - bis zum Abschluss des ersten Abrechnungsjahrs nach neuer Nebenkostenregelung bereits Nachzahlungen zu leisten wären.
7.4.2. Die Beschwerdeführer rügen diese Erwägungen als in mehrfacher Hinsicht unzutreffend:
7.4.2.1. Sie werfen der Vorinstanz zunächst vor, sie gehe davon aus, alleine aufgrund der Aussage der Beschwerdegegnerin und des Formulierungsvorschlags aus dem SVIT-Kommentar habe Letztere alle notwendigen Angaben offengelegt, aufgrund derer die Beschwerdeführer hätten erkennen können, ob eine Änderung kostenneutral sei. Das Bundesgericht habe indes in <ref-ruling> ausdrücklich festgehalten, die blosse Aussage der Vermieter erlaube einem Mieter nicht, entsprechende Schlüsse zu ziehen, ob der Mietzins gemäss den verlangten Akontozahlungen herabgesetzt worden sei.
Die Beschwerdeführer missverstehen damit die Erwägungen des Bundesgerichts im zitierten Entscheid: Dessen Ausführungen zufolge gab die Vermieterin in jenem Fall bloss an, der Mietzins werde im Verhältnis zu den geforderten Akontozahlungen herabgesetzt (siehe <ref-ruling> E. 3.3 S. 366 in initio). Das Gericht kritisierte, der Mieter habe damit keinen Anhaltspunkt, der es ihm ermögliche, zu beurteilen, inwieweit die Akontozahlungen den tatsächlich anfallenden Kosten entsprächen. Wenngleich es sicherlich nicht möglich sei, die tatsächlichen Kosten im Voraus genau zu beziffern, müsse der Mieter zumindest über die bisher angefallenen Kosten informiert werden (zum Ganzen <ref-ruling> E. 3.3 S. 366). Dass es sich bei der Mitteilung um eine - wie die Beschwerdeführer monieren - "blosse Aussage der Vermieter" handelt, steht der Gültigkeit der Ankündigung nicht entgegen. Nicht vorausgesetzt ist dieser Rechtsprechung zufolge insbesondere, dass der Vermieter diese Angabe beispielsweise durch Beilage von Rechnungen früherer Jahre belegt.
7.4.2.2. Weiter bringen die Beschwerdeführer hiergegen vor, in <ref-ruling> E. 3.1 werde ausgeführt, die Formularanzeige müsse für jeden einzelnen Posten der Betriebskosten Berechnungen enthalten, welche einen Vergleich zwischen den bisher im Nettomietzins enthaltenen und den neuen separat abgerechneten Kosten erlaube. Der Vermieter habe im erwähnten Bundesgerichtsentscheid mit Hinweis auf <ref-law> vorgebracht, bei einer Mietzinserhöhung wegen Kostensteigerung oder Mehrleistung hätten keine Einzelheiten der Renditeberechnung mitgeliefert werden müssen, weshalb dasselbe auch bei der Ausgliederung von Nebenkosten aus dem Nettomietzins gelten müsse. Diese Ansicht habe das Bundesgericht mit der Begründung verworfen, dass sich bei Mietzinserhöhungen wegen Kostensteigerungen oder Mehrleistungen aus dem Vergleich von altem und neuem Mietzins das Ausmass der Vertragsänderung ohne Weiteres ergebe, während dies bei der Ausscheidung von Nebenkosten nicht zutreffe, da der Mieter die bisherigen im Mietzins enthaltenen tatsächlichen Kosten nicht kenne.
Zunächst ist festzuhalten, dass die Beschwerdeführer in der Erwägung 3.1 des von ihnen zitierten Bundesgerichtsentscheids unzutreffenderweise eine derartige Aussage des Bundesgerichts erblicken, hat es darin doch bloss den Standpunkt der dortigen Beschwerdeführerin zusammengefasst, welche die Erwägungen der dortigen Vorinstanz kritisierte, wonach die Mitteilung der Vertragsänderung Berechnungen für jeden einzelnen Posten enthalten müsse, ohne diesen dort jedoch zu beurteilen. Die Forderung der Beschwerdeführer, die Beschwerdegegnerin hätte für jede einzelne ausgeschiedene Nebenkostenposition den bisher auf diese entfallenen Betrag und dessen Berechnung angeben müssen, findet indes auch in den sonstigen Erwägungen von <ref-ruling> keine Stütze. Dies gilt insbesondere auch für die Weigerung, aus <ref-law> e contrario abzuleiten, dass die Mitteilung keine Berechnungen enthalten müsse (<ref-ruling> E. 3.1 S. 363 in fine i.V.m. E. 3.3 S. 367). Entscheidend ist bloss, dass der Mieter weiss, welche Positionen aus dem Mietzins ausgegliedert werden und welche Kosten diese bisher verursacht haben, damit er beurteilen kann, ob die Höhe der neuen Akontozahlungen den tatsächlichen Aufwendungen entspricht, beziehungsweise, ob der Mietzins ansteigen wird (<ref-ruling> E. 3.2.1 S. 365; siehe auch E. 7.1 hiervor). Um diese Beurteilung vornehmen zu können, muss er nicht den Aufwand kennen, der bislang für jede einzelne Position gesondert anfiel; es reicht aus, wenn er um den Gesamt betrag weiss.
7.4.2.3. Die Beschwerdeführer rügen schliesslich, die Vorinstanz gehe ohne Beleg davon aus, der Betrag, um welchen der Nettomietzins gesenkt wurde, entspreche den tatsächlich angefallenen Kosten sämtlicher erwähnter Positionen und weil sie unbewiesen annehme, der von der Beschwerdegegnerin gewählte Einjahresdurchschnitt gewährleiste eine kostenneutrale Nebenkostenausscheidung. Wie sich aus den Nachzahlungen von 2008/09 bis 2015/16 zeige, sei auch in dieser Periode eine Nachzahlung von bloss Fr. 199.85 angefallen, was das Argument der Beschwerdegegnerin widerlege, die Kosten seien rein teuerungsbedingt nach 15 Jahren angestiegen. Wenn die Beschwerdegegnerin die Nebenkosten bis 2011/12 nicht ausgeschieden hätte und die Beschwerdeführer im Vorjahr einzig die Nachzahlung von Fr. 199.85 zusätzlich zum Mietzins hätten zahlen müssen, hätte die Beschwerdegegnerin den Nettomietzins 2011/12 nach ihrer Version (d.h. bei Abstellen lediglich auf die Vorjahresperiode) nur im Umfang von Fr. 195.65 senken müssen (Fr. 199.85 / 12 Mt. = Fr. 16.65; Fr. 179.-- [= ausgegliederte Kosten; siehe Sachverhalt A.a] + Fr. 16.65 = Fr. 195.65), wohingegen bei Heranziehen des Durchschnitts der letzten drei Jahre, die Senkung Fr. 217.65 hätte betragen müssen.
Mit dieser Argumentation vermischen die Beschwerdeführer die Frage, ob der Vermieter seiner Begründungspflicht nach <ref-law> nachgekommen ist mit jener nach der materiellen Missbräuchlichkeit der Vertragsänderung nach <ref-law>: Unter der Geltung von <ref-law> ist nicht von Bedeutung, ob die Nebenkostenausscheidung kostenneutral erfolgt; entscheidend ist bloss, ob der Vermieter diese - entsprechend der zitierten Rechtsprechung (E. 7.1 hiervor) - hinreichend begründet. Gibt der Vermieter - wie vorliegend - etwa an, dass er den Mietzins im Umfang des im Vorjahr auf die auszugliedernden Nebenkosten entfallenen Betrags reduziere, genügt er seiner Begründungspflicht genauso wie jener, der auf einen Mehrjahresdurchschnitt abstellt und dies offenlegt. Die Frage nach der Kostenneutralität der Ausgliederung kann sich indes in einem Anfechtungsverfahren stellen, wenn geltend gemacht wird, durch die Ausgliederung werde der Mietzins indirekt erhöht, was zu einem missbräuchlichen Mietzins führte. Für ein solches Verfahren wird in der Lehre vertreten, dass zur Beurteilung, ob die Ausgliederung kostenneutral erfolgt sei, grundsätzlich auf die Kosten mehrerer Jahre abzustellen sei (etwa BISANG UND ANDERE, a.a.O., N. 69 zu <ref-law>; Beat Rohrer, in: Das schweizerische Mietrecht, 4. Aufl. 2018, N. 76 zu <ref-law>; derselbe, Nebenkosten - Frais accessoires, MRA 3/08 S. 108 f.; MARKUS WYTTENBACH, Nebenkosten, in: Wohn- und Geschäftsraummiete, Handbücher für die Anwaltspraxis, 2016, S. 278 RZ. 6.70). Da die Frage nach der Missbräuchlichkeit der Mietzinserhöhung nicht Verfahrensgegenstand ist, ist nicht weiter darauf einzugehen, anhand welcher Zahlen zu beurteilen ist, ob die Ausgliederung kostenneutral erfolgte.
7.5. Im Lichte der vorstehenden Ausführungen erfüllte die Beschwerdegegnerin damit die Voraussetzungen an eine klare Begründung im Sinne von Art. 269d Abs. 3 i.V.m. Art. 19 Abs. 1 lit. b Ziff. 3 VMWG, weshalb die Vertragsänderung nicht nichtig ist. Mangels Nichtigkeit der Vertragsänderung steht den Beschwerdeführern auch der geltend gemachte Rückerstattungsanspruch nicht zu, weshalb dieses Begehren ebenfalls abzuweisen ist.
8.
Die Beschwerdeführer begehren eventualiter, die Beschwerdegegnerin sei zu verpflichten, ihnen "korrekte Nebenkostenabrechnungen ab 2007/08 bis 2015/16 zu erstellen".
Die Vorinstanz hielt hierzu fest, dass die Beschwerdegegnerin dieses Eventualbegehren lediglich für den Fall stelle, da die Nichtigkeit der Mietzinsänderung vom 8. März 2002 bejaht würde. Da die Vorinstanz dies nicht getan habe, habe sie zu Recht das Rechtsbegehren abgewiesen.
Die Beschwerdeführer setzen sich mit dieser Begründung mit keinem Wort auseinander, sondern führen unter Verweis auf <ref-law> aus, weshalb ihnen ein derartiger Anspruch auf eine "korrekte" Nebenkostenabrechnung zustehen soll. Damit genügen sie den Begründungsanforderungen nicht (vgl. E. 2.1 hiervor).
9.
Im Ergebnis ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Dem Ausgang des Verfahrens entsprechend werden die Beschwerdeführer unter solidarischer Haftung kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und 5 sowie <ref-law>).

Demnach erkennt das Bundesgericht:
1.
Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
2.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
3.
Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
4.
Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
5.
Dieses Urteil wird den Parteien und dem Obergerichts des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 8. Februar 2021
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Hohl
Der Gerichtsschreiber: Bittel