Sachverhalt:
A.
Die B._ AG (nachfolgend: Vermieterin, Beschwerdegegnerin) schloss mit A._ und 25 weiteren Personen (nachfolgend: Mieter, Beschwerdeführer) im Frühjahr/Sommer 2012 Mietverträge über 16 Wohnungen in U._ ab. Dabei handelte es sich um Erstvermietungen. Die Mietverhältnisse wurden zwischen dem 15. Mai 2012 und dem 1. Oktober 2012 angetreten. In den Mietverträgen wurden Akontozahlungen in der Höhe von Fr. 280.-- bis Fr. 360.-- pro Monat für die ausgeschiedenen Nebenkosten vereinbart. Anfangs Juni 2014 kündigte die Vermieterin alle Mietverhältnisse ordentlich per 30. September 2014 und stellte den Mietern die Heiz- und Nebenkostenabrechnung für die Abrechnungsperiode 2012/2013 zu. Mitte Oktober 2014 folgte die Heiz- und Nebenkostenabrechnung für die Abrechnungsperiode 2013/2014.
Die Saldi der Heiz- und Nebenkostenabrechnungen für die Abrechnungsperioden 2012/2013 und 2013/2014 überstiegen die von den Mietern geleisteten Akontozahlungen erheblich. In der Folge weigerten sich die Mieter, die von der Vermieterin geltend gemachten Nachforderungen für die effektiv angefallenen Nebenkosten in dem von ihr geforderten Umfang zu bezahlen. Unbestrittenermassen erkundigten sich die Mieter im Rahmen der Vertragsverhandlungen nie bei der Vermieterin, ob die vertraglich verlangten Akontozahlungen kostendeckend sein würden. Die Vermieterin machte den Mietern auch keine dahingehende Zusicherungen.
B.
Anlässlich der Schlichtungsverhandlung vom 20. Juli 2015 anerkannten die Mieter eine Nachzahlungspflicht in der Höhe von 20 % der geleisteten Akontobeträge für Heiz-/Nebenkosten.
Am 11. September 2015 erhob die Vermieterin für die restlichen Forderungsbeträge gemäss den beiden Nebenkostenabrechnungen Klagen gegen die Mieter beim Mietgericht des Bezirks Horgen. Die verschiedenen Verfahren wurden mit Beschluss des Mietgerichts vereinigt. Mit Urteil vom 26. September 2017 hiess das Mietgericht die Klage der Vermieterin teilweise gut. Soweit die verlangten Nachzahlungen den Umfang von 30 % der in den jeweiligen Mietverträgen vereinbarten jährlichen Akontozahlungen überstiegen, wies es die Klage ab.
Eine gegen dieses Urteil gerichtete Berufung der Vermieterin hiess das Obergericht des Kantons Zürich mit Urteil vom 30. April 2018 gut. Es verpflichtete die Mieter im Wesentlichen, der Vermieterin die jeweils auf ihre Wohnung entfallenden Nebenkosten gemäss den betragsmässig anerkannten Heiz- und Nebenkostenabrechnungen zu zahlen, und zwar im vollen Umfang des Saldos nach Abzug der bereits geleisteten Akontozahlungen.
C.
Mit Beschwerde in Zivilsachen beantragen die Mieter dem Bundesgericht, das Urteil des Obergerichts aufzuheben und das Urteil des Mietgerichts zu bestätigen.
Die Beschwerdegegnerin trägt auf kostenfällige Abweisung der Beschwerde an, soweit darauf einzutreten sei. Das Obergericht hat auf Vernehmlassung verzichtet.
Das Gesuch der Beschwerdeführer um Erteilung der aufschiebenden Wirkung wurde mit Präsidialverfügung vom 22. August 2018 gutgeheissen.

Erwägungen:
1.
Strittig ist zwischen den Parteien, ob die Beschwerdegegnerin verpflichtet gewesen wäre, die Beschwerdeführer darüber aufzuklären, dass die in den Mietverträgen vereinbarten Akontozahlungen nicht kostendeckend sein würden, und ob deshalb die von der Beschwerdegegnerin geforderten Nachzahlungen entsprechend zu kürzen sind.
1.1.
1.1.1. In <ref-ruling> schützte das Bundesgericht eine Vereinbarung über Akontozahlungen, welche die tatsächlich anfallenden Nebenkosten wesentlich unterschritt. Die Mieterschaft argumentierte, sie hätte sich nach Treu und Glauben darauf verlassen dürfen, dass die vertragsgemäss geleisteten Akontozahlungen den tatsächlich anfallenden Nebenkosten ungefähr entsprächen, sodass die Nebenkosten, welche diesen Betrag massgeblich übersteigen würden, nicht geschuldet seien (<ref-ruling> E. 2 S. 26). Die effektiven Nebenkosten beliefen sich jeweils auf mehr als das Doppelte (rund 210 - 260 %) der geleisteten Akontozahlungen. Das Bundesgericht hielt fest, wenn der Mieter entsprechend der ordnungsgemäss erstellten jährlichen Nebenkostenabrechnung Nachzahlung leiste, erfülle er damit seine ursprüngliche vertragliche Pflicht zur Übernahme der Nebenkosten. Eine Vertragsänderung sei damit nicht verbunden (<ref-ruling> E. 3.2 S. 26 f.).
In welchem Verhältnis die vereinbarten Akontozahlungen zu den tatsächlich anfallenden Nebenkosten stehen müssten, sei weder in einer zwingenden noch in einer dispositiven Vorschrift des Mietrechts geregelt. Es gelte in dieser Hinsicht die Vertragsfreiheit (<ref-ruling> E. 4 S. 27 f.). Der Begriff " Akontozahlung " deute darauf hin, dass es sich bei den unter diesem Titel erbrachten monatlichen Leistungen bloss um vorläufige Zahlungen handle, die gemäss korrekt zu erfolgender Abrechnung an die jährlich aufgelaufenen und vom Mieter vertragsgemäss geschuldeten Nebenkosten anzurechnen seien (<ref-ruling> E. 5.1 S. 28). Abreden über Akontozahlungen der Nebenkosten würden vornehmlich dazu dienen, hohe Zahlungen des Mieters zu verhindern und dadurch das Inkassorisiko des Vermieters zu verringern. Nebenkosten seien dadurch gekennzeichnet, dass der Gesamtbetrag im Zeitpunkt des Vertragsschlusses unbekannt sei und von einer Abrechnungsperiode zur anderen variiere. Dabei spiele auch das Verbraucherverhalten eine Rolle (<ref-ruling> E. 5.1.1 S. 28 f.).
Obschon mancher Mieter bei Abschluss eines Mietvertrages vermuten möge, die Akontozahlungen würden zur Tilgung der aus den Nebenkosten zu erwartenden Schuld ausreichen, sei diese Erwartung im Hinblick auf die erkennbaren Unsicherheiten ohne besondere Zusicherung seitens des Vermieters nicht berechtigt und könne nicht bewirken, dass der Mieter den übersteigenden Betrag nicht oder nicht in vollem Umfang zu tragen hätte. Falls die Beschränkung der Nebenkosten auf einen bestimmten Betrag für einen Mietinteressenten eine notwendige Bedingung für den Abschluss des Mietvertrages darstelle, sei ihm zuzumuten, sich diesbezüglich zu vergewissern. Der Vermieter sei umso weniger von sich aus zur entsprechenden Aufklärung verpflichtet, je höher der Nettomietzins sei und je geringer sich im Verhältnis dazu die zu erwartende Nachzahlung ausnehme. Da es den Parteien freistehe, ob sie für die vom Mieter zu übernehmenden Nebenkosten Akontozahlungen vereinbaren wollten, müsse es auch zulässig sein, vom Mieter nur eine tief bemessene Akontozahlung zu verlangen (<ref-ruling> E. 5.1.1 S. 28 f.).
Weiter hielt das Bundesgericht fest, die analoge Anwendung der werkvertraglichen Regelung von Art. 375 Abs. 1 OR falle ausser Betracht, da die Höhe der Akontozahlungen nicht generell die Zusicherung eines ungefähren Kostenansatzes darstelle. Art. 373 Abs. 1 OR sei ebenso wenig anwendbar, könne doch im Hinblick auf die getroffene Abrechnungsabrede keine Rede davon sein, die Parteien hätten die Vergütung " zum voraus genau bestimmt " (<ref-ruling> E. 5.1.2 S. 29 f.).
Das Bundesgericht verneinte schliesslich auch eine Haftung der Vermieterin aus culpa in contrahendo, da aus den tatsächlichen Feststellungen hervorgehe, die Mieter hätten befürchtet, sie würden die Wohnung nicht erhalten, wenn sie sich über die effektive Höhe der Nebenkosten erkundigt hätten. Diese Zweifel würden sich aber nicht mit dem Argument vertragen, sie hätten mit Nebenkosten im Umfang der Akontozahlungen gerechnet. Ins Gewicht falle zudem, dass die Mieter die hohen Nachzahlungen jahrelang anstandslos bezahlt hätten (<ref-ruling> E. 6.1.2 S. 31).
1.1.2. Das Bundesgericht erwog im Sinne der dargelegten Rechtsprechung (vgl. E. 1.1.1 hiervor) in einem nicht publizierten Entscheid, ein Vermieter sei nicht verpflichtet, den Mieter während der Vertragsverhandlungen über die mutmassliche Höhe der Nebenkosten aufzuklären, und zwar selbst dann nicht, wenn diese durch die konkret vereinbarten Akontozahlungen wahrscheinlich nicht gedeckt seien. Entsprechend verneinte das Bundesgericht eine absichtliche Täuschung (Urteil 4A_268/2009 vom 4. Februar 2010 E. 2).
1.2.
1.2.1. Die Vorinstanz stellte fest, die Erstinstanz habe sich mit der bundesgerichtlichen Rechtsprechung (vgl. hiervor E. 1.1) ausführlich auseinandergesetzt. Sie habe diese kritisiert und als Argument für eine allgemeine Aufklärungspflicht des Vermieters in Bezug auf die mutmasslich effektiv anfallenden Nebenkosten die Schutzbestimmungen des Mietrechts ins Feld geführt. Die Erstinstanz habe festgehalten, das Verneinen einer solchen generellen Aufklärungspflicht des Vermieters stehe in einem Spannungsverhältnis zu zahlreichen Mieterschutzbestimmungen. Durch das Festsetzen von zu tiefen Akontozahlungen könne ein Vermieter namentlich die in Art. 270 Abs. 1 OR vorgesehene Möglichkeit des Mieters zur Anfechtung des Anfangsmietzinses vereiteln, da die Anfechtungsfrist in dem Zeitpunkt, in welchem der Mieter die Nebenkostenabrechnung erhalte, naturgemäss bereits verstrichen sei. Gleich verhalte es sich mit dem Zweck von Art. 18 der Verordnung vom 9. Mai 1990 über die Miete und Pacht von Wohn- und Geschäftsräumen (VMWG; SR 221.213.11) : Für den Mieter spiele es faktisch keine Rolle, ob er aufgrund einer einseitigen Vertragsänderung oder aber aufgrund von nicht kostendeckend eingesetzten Akontobeträgen höhere Kosten tragen müsse.
1.2.2. Die Vorinstanz erkannte dagegen, eine Anfechtung des Anfangsmietzinses nach Art. 270 Abs. 1 lit. b OR wäre für die Beschwerdeführer ohnehin nicht möglich gewesen, da es sich um Erstvermietungen gehandelt habe. Aber auch in Fällen, in welchen Art. 270 Abs. 1 lit. b OR anwendbar sei, könne der Vermieter zwar theoretisch den Nettomietzins erhöhen bei gleichzeitiger Herabsetzung der Akontozahlungen für die Nebenkosten, indes habe er aber dem neuen Mieter gemäss Art. 256a Abs. 2 OR die Höhe des Mietzinses des vorangegangenen Mietverhältnisses mitzuteilen, und zwar einschliesslich der Nebenkosten. Würden dem Mieter diese Angaben nicht genügen, könne er beim Vermieter zusätzliche Informationen über die Nebenkosten erfragen. Insofern könne ein Mieter durchaus erkennen, wenn ein Vermieter bei der Neuvermietung plötzlich einen höheren Nettomietzins erhebe, demgegenüber aber die Nebenkosten erheblich gesenkt oder neue Nebenkosten ausgeschieden habe. In diesem Fall könne der Mieter beim Vermieter nachhaken und sich erkundigen, weshalb die Akontozahlungen für die Nebenkosten herabgesetzt worden seien. Bestehe dafür kein mit dem Gebrauch des Mietobjekts zusammenhängender objektiver Anlass, müsse der Mieter davon ausgehen, die Akontozahlungen seien nicht mehr kostendeckend. Er könne dann den Anfangsmietzins rechtzeitig innert der 30-tägigen Frist von Art. 270 Abs. 1 lit. b OR anfechten. Das Mietrecht biete folglich genügend Handhabe, um einer Umgehung der Anfechtungsmöglichkeit des Anfangsmietzinses zu begegnen.
Weiter stellte die Vorinstanz fest, die Kritik an der Rechtsprechung des Bundesgerichts sei auch insoweit unberechtigt, als sie sich auf Art. 18 VMWG abstütze. Nach dieser Bestimmung hat ein Vermieter einen Vorbehalt in Franken oder Prozenten des Mietzinses festzulegen, wenn er eine ihm zustehende Mietzinsanpassung nicht vollständig geltend macht. Bei der Nachforderung von Nebenkosten, die nicht durch die geleisteten Akontozahlungen gedeckt seien, handle es sich nicht um die Ausschöpfung eines Vorbehaltes und somit nicht um eine Vertragsänderung im Sinne von Art. 269d OR. Vielmehr werde vom Mieter bloss die Erfüllung seiner bereits mit Unterzeichnung des Mietvertrages eingegangenen Pflicht zur Bezahlung der ausgeschiedenen Nebenkosten verlangt.
1.2.3. Die Vorinstanz hielt mit der Erstinstanz fest, das Bundesgericht habe sich in seiner Rechtsprechung (vgl. hiervor E. 1.1) nicht für eine einzelfallunabhängige Verneinung der Aufklärungspflicht ausgespro-chen. Es sei somit im Einzelfall aufgrund der konkreten Umstände zu prüfen, ob den Vermieter eine Aufklärungspflicht getroffen habe. Die Erstinstanz habe aber im Folgenden nicht einzelfallbezogen argu-mentiert, sondern mit allgemeinen Überlegungen für eine generelle Aufklärungspflicht des Vermieters in Bezug auf die mutmassliche Höhe der effektiv anfallenden Nebenkosten. Wer sich auf den Vertrauensschutz berufe und daraus eine gesetzlich nicht vorge-sehene Aufklärungspflicht ableiten wolle, müsse sich aber auf besondere Umstände stützen können, die aus objektiver Sicht ein berechtigtes Vertrauen hervorzurufen vermögen. Denkbar wäre dies beispielsweise dann, wenn ein Mieter dem Vermieter im Rahmen der Vertragsverhandlungen explizit mitteile, die effektiv zu bezahlenden Nebenkosten dürften einen gewissen Maximalbetrag nicht überschreiten, andernfalls er den Mietvertrag nicht eingehen könne. Einzelfallbezogene, vertrauensbildende Umstände, die zu einer Aufklärungspflicht der Beschwerdegegnerin geführt hätten, seien durch die Beschwerdeführer weder behauptet noch belegt.
1.2.4. Zusammenfassend erwog die Vorinstanz, weder die Missbrauchsproblematik noch die Umstände des konkreten Einzelfalls vermöchten eine Aufklärungspflicht der Beschwerdegegnerin zu begründen. Sie sei weder aus Gesetz, Vertrag noch nach Treu und Glauben und den herrschenden Anschauungen dazu verpflichtet gewesen, die Beschwerdeführer über die Höhe der mutmasslich effektiv anfallenden Nebenkosten von sich aus zu informieren. Ebensowenig sei sie verpflichtet gewesen, die Beschwerdeführer auf mutmasslich nicht kostendeckend vereinbarte Akontozahlungen für die Nebenkosten hinzuweisen. Es liege somit auch keine absichtliche Täuschung vor.
1.3. Die Beschwerdeführer rügen in Anlehnung an die Ausführungen der Erstinstanz (vgl. hiervor E. 1.2.1), die Annahme von Vertrags-freiheit betreffend die Festsetzung von Akontobeträgen verstosse gegen zwingende Bestimmungen des mietrechtlichen Preisschutzes respektive höhle diese aus. Es sei deshalb von einer Aufklärungs-pflicht des Vermieters auszugehen. Diese Aufklärungspflicht leite sich ab aus dem (mietrechtlichen) Vertrauensschutz, der generell bei der Festsetzung des Mietzinses gelte, aus dem Grundgedanken von Art. 18 VMWG, welcher diesen Vertrauensschutz konkretisiere, dem Grundsatz der culpa in contrahendo, sowie dem Schutzgedanken von Art. 270 OR und Art. 257a OR.
1.4. Die Beschwerde zielt auf eine Änderung der Rechtsprechung von <ref-ruling> (vgl. hiervor E. 1.1). Nach konstanter Praxis muss sich eine Praxisänderung auf ernsthafte, sachliche Gründe stützen können, die - vor allem im Hinblick auf das Gebot der Rechtssicherheit - umso gewichtiger sein müssen, je länger die als falsch oder nicht mehr zeitgemäss erkannte Rechtsanwendung für zutreffend erachtet worden ist. Eine Praxisänderung lässt sich grundsätzlich nur begründen, wenn die neue Lösung besserer Erkenntnis der ratio legis, veränderten äusseren Verhältnissen oder gewandelten Rechtsanschauungen entspricht, andernfalls ist die bisherige Praxis beizubehalten (<ref-ruling> E. 3a S. 292 f.; <ref-ruling> E. 4 S. 777; <ref-ruling> E. 10 S. 79; Urteil 5A_324/2016 vom 1. Dezember 2016 E. 2).
1.5.
1.5.1. <ref-ruling> ist in der Lehre teilweise auf Kritik gestossen (ROGER WEBER, in: Basler Kommentar, Obligationenrecht, 6. Aufl. 2015, N. 2a zu Art. 257b OR; ANDREAS BÉGUIN, in: Mietrecht für die Praxis, 9. Aufl. 2016, S. 338 ff.; ISABELLE BIERI, in: Droit du bail à loyer et à ferme, 2. Aufl., N. 56 zu Art. 257a/257b OR; TOBIAS BRÄNDLI, Nebenkosten: Rechtliche Grenzen bei der Verteilung, mp 2016, S. 281 ff., 287 f.; RICHARD PÜNTENER, Der Vertrauensschutz bei der Mietzins- und Nebenkostengestaltung, mp 2006 S. 1 ff.; ANITA THANEI, Zu tief angesetzte Nebenkosten als absichtliche Täuschung - Kommentar zu einem Bundesgerichtsentscheid, mp 2005, S. 232 ff.; MICHEL BISE, Les bons acomptes font les bons amis, in: Mélanges en l'honneur de Pierre Wessner, 2011, S. 291 ff., 296 ff.).
WEBER hält beispielsweise fest, die Begründung des Entscheides überzeuge nicht. Die Erwartung des Mieters bei Vertragsabschluss, die Akontozahlungen würden in etwa zur Bestreitung der Kosten ausreichen, sei vernünftig. Sie lasse sich nicht einfach unter Hinweis auf die für den Vermieter bestehenden Unsicherheiten als unberechtigt bezeichnen. Diese würden genau betrachtet keine Rolle spielen. Da vertragliche Vereinbarungen immer im Lichte der historischen Kenntnisse der Parteien zu beurteilen seien, dürfe der Vermieter sich selbstverständlich darauf berufen, die Kosten für Drittleistungen hätten sich seither erhöht oder der neue Mieter verursache viel höhere Kosten als der Vorgänger (WEBER, a.a.O., N. 2a zu Art. 257b OR). Wenn Akontozahlungen der Minimierung des Inkassorisikos des Vermieters als Gläubiger dienten, so dürfe der Mieter als Schuldner nach Treu und Glauben auch annehmen, der Vermieter werde diesen
Zweck nicht durch viel zu tiefe Akontozahlungen unterlaufen (WEBER, a.a.O., N. 2a zu Art. 257b OR; BÉGUIN, a.a.O., S. 338; BRÄNDLI, a.a.O., S. 287).
Weiter wird kritisiert, das Bundesgericht habe zu Unrecht angenommen, dem Vermieter sei bei Vertragsabschluss der Gesamtbetrag der Nebenkosten (noch) nicht bekannt. Diese Auffassung decke sich nicht mit den betriebswirtschaftlichen Realitäten, denn der Vermieter kenne die Kosten aufgrund von früheren Abrechnungen oder im Falle von Erstvermietungen aufgrund von Erfahrungswerten bzw. könne diese abschätzen (BÉGUIN, a.a.O., S. 339; PÜNTENER, a.a.O., S. 15; BRÄNDLI, a.a.O., S. 287 f.). Der Vermieter verfüge bei Vertragsabschluss über einen Informationsvorsprung, da er allein die Kosten kenne, und habe deshalb gegenüber dem Mieter als schwächere Vertragspartei eine besondere Aufklärungspflicht über Umstände, die der Mieter nicht kennen könne. Vom Mieter zu verlangen, sich bei Vertragsschluss nach der Höhe der Nebenkosten zu erkundigen, ansonsten jegliche Nachzahlung zu akzeptieren sei, lasse sich mit dem Sozialschutzgedanken und dem im Bereich der Mietzinsgestaltung geltenden Vertrauensschutz nicht in Einklang bringen (BÉGUIN, a.a.O., S. 339 f.; THANEI, a.a.O., S. 233; PÜNTENER, a.a.O., S. 15 ff.).
Hinzu komme, dass das Erfordernis der besonderen Vereinbarung der Nebenkosten in Art. 257a Abs. 2 OR gerade dem Zweck diene, den Mieter vor unabsehbaren Forderungen unter dem Titel "Nebenkosten" zu schützen (WEBER, a.a.O., N. 2a zu Art. 257b OR). BÉGUIN argumentiert weiter - ähnlich wie dies die Erstinstanz erkannte (vgl. hiervor E. 1.2.1) - die Auffassung des Bundesgerichts stünde auch im Widerspruch zur ratio legis von Art. 270 OR (BÉGUIN, a.a.O., S. 340).
1.5.2. Ein anderer Teil der Lehre stimmt <ref-ruling> zu (HANS GIGER, Berner Kommentar, N. 59 ff. zu Art. 257a OR; PETER HIGI, Bemerkungen zu <ref-ruling>, AJP 2006 S. 601 ff.; BEAT ROHRER, Nebenkosten, MRA 2008 S. 101 ff., 106 ff.; JEAN-PIERRE TSCHUDI, Müssen Akontozahlungen für Nebenkosten den mutmasslichen effektiven Kosten entsprechen?, mp 2005 S. 169 ff.; MAJA L. BLUMER, in: Kurzkommentar Obligationenrecht, 2014, N. 8 zu Art. 257a/257b OR; wohl auch IRENE BIBER, in: Das Schweizerische Mietrecht, 4. Aufl. 2018, N. 41 ZU Art. 257-257b OR). So argumentiert GIGER, Art. 257a Abs. 2 OR stelle keinerlei Regeln dazu auf, in welcher Art separat vereinbarte Nebenkosten zu bezahlen seien und die Parteien seien auch nicht verpflichtet, Akontozahlungen zu vereinbaren. Unabhängig davon seien - bei entsprechender Abrede - die Nebenkosten aber am Ende der Abrechnungsperiode geschuldet (GIGER, a.a.O., N. 59 zu Art. 257a OR). Die <ref-ruling> zustimmende Lehre hält weiter fest, es lasse sich nicht sagen, die Vereinbarung von Akontozahlungen stelle eine Zusicherung des Vermieters dar, die noch unbestimmbaren Nebenkosten würden nicht wesentlich über dem zu liegen kommen, was im Vertrag als Anzahlung bestimmt wurde. Es sei einem Mietinteressenten, gerade mit Blick auf Treu und Glauben zuzumuten, sich nach den effektiven bisherigen bzw. früheren Kosten zu erkundigen (HIGI, a.a.O., S. 605).
1.6. An der in <ref-ruling> begründeten (und mit zit. Urteil 4A_268/2009 bestätigten) Praxis ist festzuhalten.
1.6.1. Die Voraussetzungen für eine Praxisänderung (vgl. hiervor E. 1.4) sind streng. Vorliegend ist namentlich zu berücksichtigen, dass der Entscheid aus dem Jahre 2005 stammt und am 4. Februar 2010, also vor noch nicht allzu langer Zeit, bestätigt wurde. Zudem sind viele der Argumente für eine generelle Aufklärungspflicht des Vermieters betreffend die tatsächliche Höhe der Nebenkosten nicht neu, sondern wurden bereits im Präjudiz berücksichtigt und abschlägig beschieden (vgl. PETER FERTIG, O ffene Fragen bei den Nebenkosten, mp 1999, S. 67 ff., 73 ff. [der in <ref-ruling> explizit zitiert wurde]). Die Voraussetzungen einer Praxisänderung sind nicht erfüllt.
1.6.2. Der Praxis des Bundesgerichts liegt die zutreffende Annahme zugrunde, dass weder das Gesetz noch die VMWG in einer zwingenden oder dispositiven Vorschrift regeln, in welchem Verhältnis die vereinbarten Akontozahlungen zu den tatsächlich anfallenden Nebenkosten stehen müssen (<ref-ruling> E. 4 S. 27). Entgegen der Ansicht der Beschwerdeführer lässt sich eine solche Regelung auch nicht implizit aus dem Schutzzweck von mietrechtlichen Vorschriften (insbesondere den Preisschutzvorschriften) ableiten.
1.6.2.1. Die Beschwerdeführer machen erneut geltend, mit der Annahme von Vertragsfreiheit betreffend die Festsetzung der Höhe der Akontozahlungen würde die Bestimmungen über die Anfechtung des Anfangsmietzinses ausgehöhlt. Die Beschwerdeführer substanziieren nicht, wie ein Vermieter konkret durch das Festsetzen von zu tiefen Akontozahlungen die in Art. 270 Abs. 1 OR vorgesehene Möglichkeit zur Anfechtung des Anfangsmietzinses vereiteln kann. Eine Anfechtung ist nur möglich, wenn der Vermieter aus der Mietsache einen übersetzten Mietertrag erzielt. Nebenkosten müssen aber klar, detailliert und verständlich ausgeschieden werden, damit sie dem Mieter gesondert in Rechnung gestellt werden können (Art. 257a Abs. 2 OR; <ref-ruling> E. 4.3 S. 595). Weiter ist der Vermieter nach Art. 257b Abs. 1 OR nur berechtigt, die tatsächlichen Aufwendungen, das heisst die ihm effektiv entstehenden Kosten, auf den Mieter zu überwälzen. Die Beschwerdeführer zeigen denn auch nicht auf, inwiefern die Höhe der tatsächlichen Nebenkosten dazu führen sollte, dass die Beschwerdegegnerin aus der Mietsache einen übersetzten Mietertrag erzielt. Sie machen auch nicht geltend, sie hätten im Falle einer Aufklärung über die tatsächlichen Nebenkosten den Anfangsmietzins gemäss Art. 270 Abs. 1 lit. a OR als missbräuchlich angefochten und damit Aussicht auf Erfolg gehabt.
1.6.2.2. Betreffend die Vorbehaltspflicht gemäss Art. 18 VMWG ist mit der Vorinstanz (vgl. E. 1.2.2 hiervor) festzuhalten, dass es sich bei der Nachforderung von Nebenkosten, die nicht durch die geleisteten Akontozahlungen gedeckt sind, nicht um eine Ausschöpfung eines Vorbehalts und somit nicht um eine Vertragsänderung im Sinne von Art. 269d OR handelt. Bereits in <ref-ruling> hielt das Bundesgericht fest, wenn der Mieter entsprechend der ordnungsgemäss erstellten jährlichen Nebenkostenabrechnung Nachzahlung leiste, erfülle er seine vertragliche Pflicht zur Übernahme der Nebenkosten, was keine Vertragsänderung darstelle (<ref-ruling> E. 3.2 S. 26 f.).
1.6.2.3. Auch aus Art. 257a Abs. 2 OR ergibt sich - entgegen den Beschwerdeführern - nicht, dass die Akontozahlungen den tatsächlichen Nebenkosten entsprechen müssen. Die Bestimmung legt lediglich fest, dass Nebenkosten nur bei besonderer Vereinbarung zu bezahlen sind. Vielmehr müsste der Vertrag (namentlich die Nebenkostenabrede) im Einzelfall geprüft und die Willensäusserungen der Parteien nach dem Vertrauensprinzip ausgelegt werden (HANS GIGER, a.a.O., N. 61 zu Art. 257a OR).
1.6.3.
1.6.3.1. Die Beschwerdeführer berufen sich auf eine Haftung für culpa in contrahendo wegen mangelnder Aufklärung. Eine Haftung aus culpa in contrahendo setzt nach der Rechtsprechung des Bundesgerichts voraus, dass der Gegenpartei etwas verschwiegen wird, das sie nicht kennt und auch nicht zu kennen verpflichtet ist; niemand ist gehalten, im Interesse des Vertragspartners umsichtiger zu sein, als dieser selbst ist. Jede Vertragspartei hat in Vertragsverhandlungen ihre Interessen grundsätzlich selbst wahrzunehmen und kann sich nicht einfach auf deren Berücksichtigung durch den Verhandlungspartner verlassen (<ref-ruling> E. 2 S. 84; <ref-ruling> E. 5a S. 336). Dies gilt grundsätzlich auch im Mietrecht (vgl. TSCHUDI, a.a.O., S. 177 f.). Eine generelle Aufklärungspflicht des Vermieters lässt sich - entgegen den Beschwerdeführern - auch nicht aus dem blossen Umstand herleiten, der Mietvertrag qualifiziere als Dauerschuldverhältnis und das Mietrecht bilde überdies Bestandteil der Sozialschutzgesetzgebung.
Eine Haftung des Vermieters aus culpa in contrahendo würde notwendigerweise voraussetzen, dass er dem Mietinteressenten verschweigt, dass die festgesetzten Akontozahlungen angesichts der tatsächlich zu erwartenden Nebenkosten zu tief sind. Dies bedingt aber, dass der Vermieter die Höhe der tatsächlichen Nebenkosten kennt bzw. abschätzen kann. Dabei ist zu beachten, dass sich die Höhe der effektiven Nebenkosten auch nach dem tatsächlichen Verbrauch richtet, der massgeblich vom Mieterverhalten beeinflusst wird. Auch die Kosten von Drittleistungen (z.B. für Heizöl) können von einer Abrechnungsperiode zur anderen stark schwanken (<ref-ruling> E. 5.1.1 S. 28). Vorliegend handelt es sich zudem um eine Erstvermietung. Es ist fraglich, ob bei Erstvermietungen überhaupt Kenntnis des Vermieters über die Höhe der tatsächlichen Nebenkosten vorliegt. Die Vorinstanz hat offengelassen, ob die Beschwerdegegnerin - wie von den Beschwerdeführern behauptet und von der Erstinstanz als erwiesen erachtet - vor Abschluss der Mietverträge Kenntnis von einem durch die C._ AG erstellten Budget für die behaupteterweise baugleichen, von ihr als Stockwerkeigentumseinheiten verkauften Nachbarliegenschaften hatte und/oder über anderweitige Schätzungen der mutmasslich anfallenden tatsächlichen Nebenkosten verfügte. Die Beschwerdegegnerin macht in ihrer Beschwerdeantwort geltend, sie hätte die tatsächlich zu erwartenden Nebenkosten nicht abschätzen können. Die Frage kann auch vorliegend offenbleiben.
Denn eine weitere Voraussetzung einer Haftung aus culpa in contrahendo wegen mangelnder Aufklärung wäre, dass dem Mieter etwas verschwiegen wird, was er nicht kennt und auch nicht kennen kann. Wie bereits die Vorinstanz zutreffend festhält, trifft die Pflicht zum Handeln nach Treu und Glauben beide Parteien gleichermassen. Es ist daher zu prüfen, ob es einem Mietinteressenten möglich und zumutbar ist, sich beim Vermieter nach der Höhe der zu erwartenden tatsächlichen Nebenkosten zu erkundigen.
Die Beschwerdeführer machen diesbezüglich geltend, es sei für einen Mietinteressenten nicht zumutbar, in Mietvertragsverhandlungen Nachfragen nach der Höhe der tatsächlich zu erwartenden Nebenkosten zu stellen, wenn er sich - wie beispielsweise in der Stadt Zürich und der näheren Agglomeration - neben 50 weiteren Interessenten um eine neue Wohnung bewerben wolle. Die Vorstellung einer vorvertraglichen Korrespondenz zwischen Vermieter und Mietinteressenten möge schön anmuten, komme jedoch nur für schwer vermietbare Wohnungen des oberen Preissegments in Frage.
Die Beschwerdeführer übergehen, dass das (bewusste) Verschweigen der Höhe der tatsächlich zu erwartenden Nebenkosten bzw. das Festsetzen von zu tiefen Akontobeträgen durch den Vermieter, mit dem Ziel, den Eindruck eines günstigeren Mietzinses zu erwecken, nur bei schwer vermietbaren Mietobjekten überhaupt einen Sinn ergibt (vgl. FERTIG, a.a.O., S. 69). Falls - wie in dem von den Beschwerde-führern beschriebenen Beispiel - Wohnungsknappheit herrscht und sich viele Mietinteressenten um ein Mietobjekt bewerben, hat ein Vermieter keinen Anreiz, auf diese Weise den Eindruck günstigerer Mietkosten zu erwecken, um potentielle Mietinteressenten anzulocken, zumal der Vermieter das Inkassorisiko für die tatsächlich anfallenden Nebenkosten trägt. Die Beschwerdeführer machen vorliegend denn auch keine Anhaltspunkte dafür geltend, dass die entsprechenden Mietobjekte zum effektiven Bruttomietzins nicht hätten vermietet werden können. Bei schwer vermietbaren Wohnungen, wie beispiels-weise Mietobjekten des oberen Preissegments oder aber Mietobjekten an Orten mit geringer Nachfrage, wo dieser Anreiz potentiell bestehen mag, ist es dem Mietinteressenten aber umgekehrt ohne Weiteres möglich und zumutbar, sich beim Vermieter nach der Höhe der tatsächlichen Nebenkosten zu erkundigen. Das Argument der Be-schwerdeführer, eine Nachfrage des Mietinteressenten beim Vermieter sei faktisch ausgeschlossen, weil dann der Mietvertrag nicht zustande komme, stösst daher ins Leere. So zeigen die Beschwerdeführer in ihrer Beschwerde denn auch nicht auf, dass es ihnen im konkreten Fall bzw. der vorhandenen Nachfrage nicht möglich gewesen wäre, sich beim Vermieter nach der Höhe der tatsächlichen Nebenkosten zu erkundigen bzw. dass dieses Nachfragen das Zustandekommen der Mietverträge gefährdet hätte.
1.6.3.2. Die Beschwerdeführer machen weiter geltend, bejahe man ein täuschendes Verhalten durch Schweigen (Verletzung einer Aufklärungspflicht), liege auch eine absichtliche Täuschung im Sinne von Art. 28 OR vor. Die Beschwerdeführer legen in ihrer Beschwerde nicht rechtsgenügend dar, dass die Voraussetzungen einer absichtlichen Täuschung erfüllt sind, sondern verweisen auf ihre allgemeinen Ausführungen zur Begründung einer generellen Aufklärungspflicht des Vermieters. Diesbezüglich kann auf die Ausführungen zur Haftung für culpa in contrahendo verwiesen werden (vgl. hiervor E. 1.6.3.1). Die Beschwerdeführer zeigen nicht auf, dass die Beschwerdegegnerin eine Aufklärungspflicht gegenüber den Beschwerdeführern hatte. Fehlt es an einer Aufklärungspflicht, scheidet eine absichtliche Täuschung durch Schweigen von vornherein aus.
2.
Eventualiter machen die Beschwerdeführer geltend, entgegen der Ansicht der Vorinstanz lägen besondere Umstände vor, wie sie in <ref-ruling> explizit vorbehalten worden seien. Das Bundesgericht habe festgehalten, der Vermieter sei umso weniger zur entsprechenden Aufklärung von sich aus verpflichtet, je höher der Nettomietzins und je geringer sich im Verhältnis dazu die zu erwartende Nachzahlung ausnehme. Somit sei davon auszugehen, das Verhältnis von Mietzinshöhe und Nachzahlung könne ein zu berücksichtigender besonderer Umstand sein. Vorliegend würden die Nachzahlungen zu einer 13. Miete führen und seien somit erheblich. Weiter hätten die Beschwerdeführer in Anbetracht der Tatsache, dass hohe Akontobeträge vereinbart worden seien, davon ausgehen dürfen, diese entsprächen den realistischen Kosten. Schliesslich seien rund 75 % der tatsächlich geschuldeten Nebenkosten verbrauchsunabhängig, was als weiterer besonderer Umstand berücksichtigt werden müsse. Die Beschwerdegegnerin macht geltend, einige der behaupteten besonderen Umstände seien neu und daher unzulässig (namentlich, dass 75 % der tatsächlich anfallenden Nebenkosten verbrauchsunabhängig seien).
Ob der Einwand der Beschwerdegegnerin zutrifft, braucht nicht geprüft zu werden. Die von den Beschwerdeführern geltend gemachten Umstände stellen jedenfalls keine besonderen Umstände dar, welche die Beschwerdeführer hätten zur Annahme berechtigen können, sie seien nur verpflichtet, für Nebenkosten etwa den jährlichen Gesamtbetrag ihrer Akontozahlungen zu leisten (vgl. <ref-ruling> E. 5.2 S. 30). Denn als qualifizierende, besondere Umstände sind nur berechtigtes Vertrauen bildende Tatsachen zu verstehen. Die von den Beschwerdeführern geltend gemachten Tatsachen, es seien hohe Akontobeträge vereinbart worden und 75 % der Nebenkosten seien verbrauchsunabhängig gewesen, reichen dazu nicht aus. Die Beschwerdeführer machen auch nicht rechtsgenügend geltend, das Verhältnis der Nettomietzinsen und der Nachzahlungen sei hier so ausgestaltet, dass besondere Umstände vorlägen. Sie zeigen nicht auf, dass aufgrund der Nachzahlungen bei tiefen Mietzinsen eine erhebliche Erhöhung des monatlichen Mietzinses resultiert, sondern beschränken sich auf die pauschale Aussage, die Nachzahlungen würden zu einer 13. Miete führen. Die von den Beschwerdeführern geltend gemachten Tatsachen stellen weder für sich allein noch in ihrer Gesamtheit besondere Umstände im Sinne der Rechtsprechung von <ref-ruling> dar.
3.
Die Rügen der Beschwerdeführer erweisen sich als unbegründet. Die Beschwerde ist daher abzuweisen, soweit darauf eingetreten werden kann. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 Abs. 1 BGG und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 4'000.-- werden unter solidarischer Haftbarkeit den Beschwerdeführern auferlegt.
3.
Die Beschwerdeführer haben die Beschwerdegegnerin für das bundesgerichtliche Verfahren unter solidarischer Haftbarkeit mit Fr. 5'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 29. Januar 2019
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Gross