Sachverhalt:
A.
Mit Mietvertrag vom 23. September 1983 mietete A._ (Mieterin 1, Beschwerdeführerin 1) von der damaligen Eigentümerschaft ab dem 1. November 1983 eine 3-Zimmerwohnung in der Stadt Zürich. Der Mietvertrag ist viermonatlich im Voraus kündbar auf Ende März und Ende September. Der Mietzins beträgt heute Fr. 1'387.-- brutto. Mit Nachtrag zum Mietvertrag vom 17. Mai 2010 wurde B._ (Mieter 2, Beschwerdeführer 2) ebenfalls Mietpartei. Mit Mietvertrag vom 2. Juli 2001 bzw. vom 27. Januar 2009 mieteten die Mieter zusätzlich zwei Mansardenzimmer im gleichen Stockwerk zu einem Mietzins von Fr. 115.-- bzw. Fr. 104.-- brutto.
Mit amtlich genehmigten Formularen und Begleitbrief vom 16. November 2017 kündigte die C._ (Vermieterin, Beschwerdegegnerin) sowohl die 3-Zimmerwohnung als auch die beiden Mansardenzimmer per 31. März 2019. Im Begleitschreiben wurde mitgeteilt, eine umfassende Sanierung der Liegenschaft sei notwendig, damit die Gebäudesubstanz und die technische Infrastruktur den heutigen Anforderungen angepasst werden könnten. Nach vielen Abklärungen und Studien sei entschieden worden, das Gebäude aufwendig zu sanieren. Aufgrund des Ausmasses der Eingriffe in die vorhandene Bausubstanz und weil vorübergehend die Strom- und Wasserzufuhr unterbrochen sein werde, seien diese Arbeiten im bewohnten Zustand nicht möglich.
B.
Mit Klage vom 20. Juni 2018 beim Mietgericht des Bezirks Zürich beantragten die Mieter, es sei die Kündigung vom 16. November 2017 für ungültig zu erklären. Eventualiter sei das Mietverhältnis betreffend die 3-Zimmerwohnung und die beiden Mansardenzimmer einmalig um 48 Monate zu erstrecken. Das Mietgericht erklärte die Kündigung für gültig. In teilweiser Gutheissung des Eventualbegehrens der Mieter erstreckte es das Mietverhältnis einmalig und definitiv bis zum 30. Juni 2019.
Eine dagegen erhobene Berufung der Mieter wies das Obergericht des Kantons Zürich mit Urteil vom 18. Juni 2019 ab. Es erwog, da das Mietgericht die Frage der Gültigkeit der Kündigung auch im Lichte von <ref-law> geprüft habe, wie wenn ihm ein entsprechendes rechtzeitiges bzw. in der Klagebewilligung aufgeführtes Begehren unterbreitet worden wäre, sei den Mietern durch eine allfällig unvollständige Klagebewilligung kein Rechtsverlust entstanden. Halte die Begründung des Mietgerichts stand, erübrige es sich, auf die von den Mietern aufgeworfene Frage zur Protokollberichtigung bzw. zur unvollständigen Klagebewilligung einzugehen. Es hielt sodann fest, soweit die Mieter die Auffassung des Mietgerichts, die Kündigung habe nicht gegen den Grundsatz von Treu und Glauben verstossen, überhaupt in prozessrechtskonformer Weise beanstanden würden, seien ihre Rügen unbegründet. Auch die Festsetzung der Erstreckungsdauer sei nicht zu beanstanden.
C.
Mit Beschwerde in Zivilsachen beantragen die Mieter dem Bundesgericht, das Urteil des Obergerichts sei aufzuheben und es sei die Kündigung für ungültig zu erklären. Eventualiter sei das Mietverhältnis einmalig um 48 Monate zu erstrecken. Subeventualiter sei die Sache an die Vorinstanz zurückzuweisen. Die Beschwerdeführer haben zudem am 4. September 2019 (nach Ablauf der Beschwerdefrist) im eigenen Namen eine weitere Eingabe beim Bundesgericht eingereicht.
Die Beschwerdegegnerin beantragt, die Beschwerde unter Kosten- und Entschädigungsfolgen abzuweisen. Die Vorinstanz hat auf Vernehmlassung verzichtet. Die Beschwerdeführer haben unaufgefordert und wiederum im eigenen Namen repliziert.
Mit Präsidialverfügung vom 13. September 2019 wurde der Beschwerde antragsgemäss aufschiebende Wirkung gewährt, da sich dem weder die Vorinstanz noch die Beschwerdegegnerin widersetzten.

Erwägungen:
1.
Die Sachurteilsvoraussetzungen sind erfüllt und geben zu keinen Bemerkungen Anlass. Die nach Ablauf der Beschwerdefrist eingereichte Eingabe ist verspätet und nicht zu berücksichtigen. Unter Vorbehalt einer rechtsgenüglichen Begründung (Art. 42 Abs. 2 und <ref-law>) ist auf die Beschwerde einzutreten.
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, andernfalls wird darauf nicht eingetreten (<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, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Verletzung von Bundesrecht liegt. Die beschwerdeführende Partei soll in der Beschwerdeschrift 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. 89, 115 E. 2 S. 116).
2.2. 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; <ref-ruling> E. 1.5 S. 401). Ü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.3.
Die Begründung hat in der Beschwerdeschrift selbst zu erfolgen. Die beschwerdeführende Partei darf eine allfällige Replik nicht dazu verwenden, ihre Beschwerde zu ergänzen oder zu verbessern. Zulässig sind nur Vorbringen, zu denen erst die Ausführungen in der Vernehmlassung eines anderen Verfahrensbeteiligten Anlass geben (vgl. <ref-ruling> E. 2.2 S. 21; <ref-ruling> E. 3.3.4 S. 47).
3.
Umstritten ist zwischen den Parteien die Gültigkeit der Kündigung. Strittig ist namentlich, ob die Beschwerdegegnerin im Zeitpunkt der Kündigung über ein genügend konkretes, umsetzbares und realitätsnahes Projekt verfügt hat.
3.1.
3.1.1. Die ordentliche Kündigung eines Mietvertrags setzt keine besonderen Kündigungsgründe voraus. Mieter und Vermieter sind grundsätzlich frei, das (unbefristete) Mietverhältnis unter Einhaltung der Fristen und Termine zu kündigen (<ref-law>). Einzige Schranke bildet der Grundsatz von Treu und Glauben: Bei der Miete von Wohn- und Geschäftsräumen ist die Kündigung anfechtbar, wenn sie gegen diesen Grundsatz verstösst (<ref-law>; vgl. auch <ref-law>). Allgemein gilt eine Kündigung als treuwidrig, wenn sie ohne objektives, ernsthaftes und schützenswertes Interesse und damit aus reiner Schikane erfolgt oder Interessen der Parteien tangiert, die in einem krassen Missverhältnis zueinander stehen. Der Umstand, dass die Kündigung für den Mieter eine Härte darstellt, genügt nicht; eine solche ist nur im Hinblick auf eine Erstreckung des Mietverhältnisses nach <ref-law> relevant (<ref-ruling> E. 3.2.1 S. 92 f.; <ref-ruling> E. 4.1 S. 497; <ref-ruling> E. 2.1 S. 62; je mit Hinweisen).
Ob eine Kündigung gegen Treu und Glauben verstösst, beurteilt sich in Bezug auf den Zeitpunkt, in dem sie ausgesprochen wird (<ref-ruling> E. 3.2.1 S. 92 f.; <ref-ruling> E. 4.1 S. 497; <ref-ruling> E. 2.1 S. 62). Umst ände, die sich erst nach diesem Zeitpunkt ereignen, können eine ursprünglich zulässige Kündigung nicht im Nachhinein zu einer missbräuchlichen machen, sondern erlauben höchstens Rückschlüsse auf die Situation im Kündigungszeitpunkt (Urteile 4A_437/2018 vom 5. Februar 2019 E. 4.1.2; 4A_127/2017 vom 25. Oktober 2017 E. 3.2; je mit Hinweisen).
3.1.2. Nach bundesgerichtlicher Rechtsprechung verstösst eine Kündigung im Hinblick auf Umbau- oder Sanierungsarbeiten, die eine Weiterbenutzung des Mietobjekts erheblich einschränken, nicht gegen den Grundsatz von Treu und Glauben. Werden die geplanten Arbeiten hingegen nicht oder nur unerheblich erschwert oder verzögert, wenn die Mieterschaft im Mietobjekt verbleibt, besteht kein schützenswerter Grund für die Vermieterschaft, dennoch zu kündigen (grundlegend <ref-ruling> E. 4.2 S. 120; 4A_703/2016 vom 24. Mai 2017 E. 4.2, nicht publ. in: <ref-ruling>). Missbräuchlich ist eine solche Kündigung auch, wenn das Projekt als nicht realitätsnah oder objektiv unmöglich erscheint, namentlich weil es offensichtlich mit den Bestimmungen des öffentlichen Rechts unvereinbar ist, sodass die Vermieterschaft die notwendigen Bewilligungen mit Sicherheit nicht erhalten wird (BGE <ref-ruling> E. 4.1 S. 497 und E. 4.2.1 S. 499). Dass die Vermieterschaft bereits die nötigen Bewilligungen erhalten oder die hierzu erforderlichen Dokumente hinterlegt hat, ist für eine Gültigkeit der Kündigung aber nicht vorausgesetzt (BGE <ref-ruling> E. 4.1 S. 497 f. mit Hinweisen).
Ob der Verbleib der Mieterschaft im Mietobjekt geeignet wäre, (bautechnische und organisatorische) Erschwerungen, zusätzliche Kosten oder eine Verzögerung der Bauarbeiten nach sich zu ziehen, die über das Unerhebliche hinausgehen, hängt von den ins Auge gefassten Arbeiten ab. Die Gültigkeit der Kündigung setzt somit voraus, dass bereits im Zeitpunkt der Kündigung ein genügend ausgereiftes und ausgearbeitetes Projekt vorliegt, aufgrund dessen abgeschätzt werden kann, ob die geplanten Arbeiten eine Räumung des Mietobjekts erforderlich machen. Erfolgt eine Kündigung im Hinblick auf ein Projekt, das noch nicht so weit fortgeschritten ist, um diese Frage gestützt auf den Stand des Projekts im Zeitpunkt der Kündigung beurteilen zu können, verstösst sie gegen Treu und Glauben (BGE <ref-ruling> E. 4.2.2 S. 499 mit Hinweisen; vgl. auch <ref-ruling> E. 3.2.1 S. 93).
3.2.
3.2.1. Die Vorinstanz hielt fest, die Erstinstanz habe ihre Auffassung, wonach die Kündigung nicht gegen <ref-law> verstosse, damit begründet, dass die Beschwerdegegnerin im Zeitpunkt der Kündigung vom 16. November 2017 über ein genügend konkretes, umsetzbares und realitätsnahes Projekt verfügt habe, das nicht fern jeglicher greifbarer Realität liege und aufgrund dessen beurteilt werden könne, dass die geplanten Arbeiten durch die Anwesenheit der Mieter tangiert würden. Gemäss Erstinstanz habe im Zeitpunkt der Kündigung eine Sanierungsstudie vom 27. April 2017, ein Investitionsantrag vom 9. August 2017 über Fr. 2'500'000.-- und ein Vorprojekt vom 15. November 2017 vorgelegen, aus denen sich die Details des Projekts ergeben würden. Es sei somit - aufgrund der Vorbringen der Beschwerdeführer - zu prüfen, ob die Erstinstanz zu Recht davon ausgegangen sei, die Beschwerdegegnerin hätte im Zeitpunkt der Kündigung über ein "ausgereiftes Bauprojekt" verfügt. Die Baueingabe vom Februar 2018 aufgrund der Pläne vom 31. Januar 2018 und die Baubewilligung vom 25. April 2018 seien jedoch nicht relevant, da sie nach der Kündigung datieren würden; immerhin würden sie zeigen, dass das Projekt auch ernsthaft betrieben werde.
3.2.2. Die Vorinstanz erwog, die Beschwerdeführer würden geltend machen, sie hätten prozessual vorgebracht, dass und weshalb das Ausmass der Sanierung und die konkreten Massnahmen durch die beauftragten Architekten erstmals am 6. Februar 2018 - und damit nach der Kündigung - habe ermittelt werden können. Sie würden dazu auf die Seiten 12-26 von act. 24 (gemeint act. 22) - der Ausführungen ihres ersten Parteivortrages - verweisen. Die Begründung müsse aber dergestalt sein, dass die Berufungsinstanz sie ohne Weiteres verstehen könne. Dies setze voraus, dass die kritisierten Passagen des Entscheides wie auch die Akten, auf welche die Kritik abstütze, genau bezeichnet würden. Es bestehe in diesem Sinne zwar keine Rügepflicht aber eine Beanstandungslast. Der Verweis auf 15 Seiten einer vorinstanzlichen "Rechtsschrift" würden dieser Beanstandungslast nicht genügen.
Die Beschwerdeführer würden das Vorliegen eines ausgereiften Bauprojekts weiter dadurch verneinen, dass sie die Echtheit der von der Beschwerdegegnerin vorgelegten CAD-Grundrisszeichnungen infrage stellten. Auch für ihre Ausführungen, wonach diese CAD-Grundrisszeichnungen nachträglich erstellt und rückdatiert worden seien, würden sie in der Berufung auf ihre erstinstanzlichen Vorbringen verweisen und geltend machen, sie hätten zahlreiche Beweismittel offeriert. Gegenstand des Beweises seien aber nur streitige Tatsachen und streitig könne nur sein, was überhaupt behauptet worden sei. Für die Behauptungen würden sie - wie erwähnt - auf 15 Seiten ihrer erstinstanzlichen Ausführungen verweisen, was als Beanstandung nicht genüge. Zudem seien erstinstanzlich gestellte Beweisanträge, denen nicht entsprochen worden sei, im Berufungsverfahren zu wiederholen. Dass sich aus den der Erstinstanz vorgelegenen Plänen nicht genügend klar ergebe, was geplant sei, lasse sich zudem nicht sagen. Die Pläne genügten den Anforderungen an ein ausgereiftes Bauprojekt.
3.2.3. Weiter würden die Beschwerdeführer beanstanden, die Erstinstanz habe über die rechtserhebliche Tatsache, " ob ein Verbleib der [Beschwerdeführer] in der Wohnung für die [Beschwerdegegnerin] unzumutbar gewesen und eine Leerkündigung überhaupt erforderlich gewesen wäre ", keinen Beweis zugelassen. Bei der Zumutbarkeit und Erforderlichkeit handle es sich aber nicht um Tat-, sondern um Rechtsfragen, worüber kein Beweis zu führen sei. Die Tatsachen, worauf die Erstinstanz ihre Einschätzung gestützt habe, würden im Übrigen als zutreffend erscheinen. Damit würden sich die Beschwerdeführer nicht hinreichend auseinandersetzen. Darauf, ob der Verbleib der Mieter für die Vermieterin zumutbar wäre, komme es im Übrigen gar nicht an. Das Interesse der Vermieterin, die Mietverhältnisse aufzulösen, um die Arbeiten rasch zu erledigen, anstatt eine längerdauernde Renovationsphase in Kauf zu nehmen, sei legitim.
3.2.4. Hinsichtlich der Laservermessungen erwog die Vorinstanz, die Erstinstanz sei davon ausgegangen, dass eine Sanierungsstudie und ein Vorprojekt auch ohne Laservermessung erstellt werden könnten (wenn auch mit reduzierter Genauigkeit). Ob es zutreffe, dass die Beschwerdegegnerin die Wohnungen erst am 6. Februar 2018 mittels Laser habe vermessen lassen, habe die Erstinstanz somit als nicht rechtserheblich erachtet. Was daran falsch sein solle, sei nicht ersichtlich. Ohnehin sei nicht nachvollziehbar, weshalb eine Laservermessung nötig sein sollte, um zu entscheiden, ob beispielsweise Küchen und Badezimmer und Elektroinstallationen ersetzt werden sollen oder nicht.
3.3. Die Beschwerdeführer rügen, die Vorinstanz habe den Grundsatz des Handelns nach Treu und Glauben gemäss <ref-law> verletzt, indem sie ihre Ausführungen zur Frage, ob die Beschwerdegegnerin im Zeitpunkt der Kündigung über ein genügend konkretes, umsetzbares und realitätsnahes Projekt verfügt habe, unberücksichtigt gelassen habe. Sie hätten sich - entgegen der Vorinstanz - in ihrer Berufung durchaus mit den erstinstanzlichen Ausführungen auseinandergesetzt und nicht mit dem Verweis auf die erstinstanzliche "Rechtsschrift" begnügt. Sie hätten namentlich in Ziff. 41 der Berufung dargetan, weshalb die Erstinstanz ihre Argumentation zu Unrecht unberücksichtigt gelassen habe.
3.3.1. Mit den Begründungsanforderungen wird sichergestellt, dass sich die Berufung mit dem angefochtenen Entscheid auseinandersetzt (Urteil 4A_142/2017 vom 3. August 2017 E. 3.3). Begründen im Sinn von <ref-law> bedeutet aufzuzeigen, inwiefern der angefochtene Entscheid fehlerhaft sei (<ref-ruling> E. 4.3.1 S. 375; Urteil 4A_258/2015 vom 21. Oktober 2015 E. 2.4.1). Dieser Anforderung genügt nicht, lediglich auf die vor erster Instanz vorgetragenen Vorbringen zu verweisen, sich mit Hinweisen auf frühere Prozesshandlungen zufriedenzugeben oder den angefochtenen Entscheid in allgemeiner Weise zu kritisieren (<ref-ruling> E. 4.3.1 S. 375).
3.3.2. In Rz. 41 der Berufung machten die Beschwerdeführer geltend, sie hätten im erstinstanzlichen Verfahren substanziiert sowie mit etlichen Beweisofferten einen zu den erstinstanzlichen Erwägungen gegenteiligen Sachverhalt prozessual vorgebracht. Es sei anlässlich der Hauptverhandlung über mehrere Seiten (Verweis auf S. 12-26) ausgeführt worden, dass und weshalb das Ausmass der Sanierung und die konkreten Massnahmen durch die mit dem Sanierungsprojekt beauftragten Architekten erstmals am 6. Februar 2018 überhaupt erst ermittelt werden konnte. Dies genügt - wie die Vorinstanz zu Recht festhielt - den Begründungsanforderungen (vgl. hiervor E. 3.3.1) an die Berufung nicht. Eine hinreichende Auseinandersetzung mit den erstinstanzlichen Erwägungen findet nicht statt. Es ist nicht erkennbar und wird von den Beschwerdeführern in ihrer Beschwerde vor Bundesgericht auch nicht hinreichend dargelegt, mit welchen konkreten entscheidwesentlichen Vorbringen in der Berufung sich die Vorinstanz hätte auseinandersetzen müssen, welche bereits von der Erstinstanz angeblich nicht beachtet worden sein sollen.
Das Gesagte gilt auch hinsichtlich der Rügen der Beschwerdeführer im Zusammenhang mit den CAD-Grundrisszeichnungen. Sie zeigen nicht auf, dass sie in ihrer Berufung dargelegt hätten, welche konkreten Behauptungen sie zur angeblichen Rückdatierung der CAD-Grundrisszeichnungen gemacht hätten. Vielmehr wird in Rz. 44 der Berufung einleitend erneut pauschal auf S. 12-26 ihrer erstinstanzlichen Ausführungen verwiesen. Im Übrigen wird in der zitierten Rz. 44 der Berufung primär auf die Laservermessung Bezug genommen, welche angeblich erst am 6. Februar 2018 stattgefunden haben soll. Damit haben sich die Vorinstanzen aber durchaus auseinandergesetzt (vgl. hiervor E. 3.2.4).
Im Übrigen ist - wie die Beschwerdegegnerin zu Recht einwendet - ohnehin nicht einleuchtend, dass das zuständige Gremium bei der Beschwerdegegnerin (einer Anlagestiftung) einen Investitionsentscheid über Fr. 2'500'000.-- hätte treffen sollen, ohne das Ausmass der Sanierung zu kennen. Die Erstinstanz hielt diesbezüglich insbesondere fest, gemäss Investitionsantrag vom 9. August 2017 würden die baulichen Massnahmen u.a. den Totalersatz der Küchen und Bäder, den Einbau einer Liftanlage sowie die Integration der Mansardenzimmer in die Wohnungen umfassen. Die Diskrepanz zwischen den Plänen der Sanierungsstudie vom 27. April 2017 und dem Vorprojekt vom 15. November 2017 betreffe nur die Raumeinteilung sowie die Raumanordnung von Küche und Bad, nicht aber den Umfang der geplanten Arbeiten. Die Baueingabepläne vom 31. Januar 2018 und des Vorprojekts vom 15. November 2017 seien hingegen identisch. Es ist jedenfalls nicht ersichtlich und die Beschwerdeführer tun auch nicht hinreichend dar, inwiefern vorliegend zum Zeitpunkt der Kündigung nicht hätte abgeschätzt werden können, ob die geplanten Arbeiten eine Räumung des Mietobjekts erforderlich machen (vgl. hiervor E. 3.1.2). Etwas anderes lässt sich schliesslich - entgegen den Beschwerdeführern - auch nicht aus der angeblichen Weigerung der Beschwerdegegnerin, den Generalplanervertrag herauszugeben, ableiten, zumal eine solche Weigerung unterschiedliche Gründe haben kann.
3.4. Die Beschwerdeführer rügen weiter, die Vorinstanz habe ihr Recht auf Beweis gemäss <ref-law> verletzt, indem sie ihre im erstinstanzlichen Verfahren gestellten Beweisanträge, welche von der Erstinstanz nicht berücksichtigt worden seien, ebenfalls nicht berücksichtigt habe. Sie hätten in Rz. 41 der Berufung klar zum Ausdruck gebracht, welchen Beweisanträgen die Erstinstanz zu Unrecht nicht entsprochen habe und diese sinngemäss in ihrer Berufung wiederholt.
Die Rüge geht fehl. In Rz. 41 der Berufung verweisen die Beschwerdeführer pauschal auf das, was sie bereits erstinstanzlich vorgetragen haben. Dabei erwähnen sie zwar auch Beweismittel, welche von der Erstinstanz nicht berücksichtigt worden sein sollen. Sie führen dabei aber nicht aus, welche konkreten Behauptungen, mit welchen konkreten Beweismitteln hätten bewiesen werden sollen. Ohne substanziierte Behauptung und entsprechendem Beweisangebot ist kein Beweisverfahren durchzuführen. Fehlt es folglich an einer hinreichend detaillierten Behauptung, so unterbleibt die Beweisabnahme, da das Beweisverfahren nicht dazu dient, mangelhafte Vorbringen der Parteien zu ergänzen (Urteil 4A_50/2018 vom 5. September 2018 E. 3.2). Das Vorgehen der Vorinstanz verletzt somit kein Bundesrecht.
3.5. Nach dem Gesagten vermögen die Beschwerdeführer insgesamt nicht aufzuzeigen, dass die Vorinstanz Bundesrecht verletzt hätte, indem sie die Kündigung vom 16. November 2017 per 31. März 2019 als gültig erachtete.
4.
4.1. Die Beschwerdeführer rügen hinsichtlich der gewährten Erstreckung von einmalig drei Monaten eine Verletzung von Art. 272 und Art. 272b OR. Sie machen geltend, die lange Mietdauer (bei der Beschwerdeführerin 1 seien es 35 Jahre und beim Beschwerdeführer 2 immerhin 17 Jahre) sei für sich allein ein Härtegrund und hätte im Rahmen der Erstreckung stark zu Gunsten der Beschwerdeführer berücksichtigt werden müssen. Es sei folglich ein wesentlicher Umstand ausser Acht gelassen worden, der zwingend hätte berücksichtigt werden müssen. Die Auffassung der Vorinstanz, wonach die Erstinstanz die lange Mietdauer (mittelbar) berücksichtigt habe, sei insofern falsch, als die Erstinstanz diese - wenn überhaupt - offensichtlich nicht stark zu Gunsten der Beschwerdeführer gewichtet habe.
4.2. Nach <ref-law> kann der Mieter die Erstreckung des Mietverhältnisses verlangen, wenn die Beendigung der Miete für ihn oder seine Familie eine Härte zur Folge hätte, die durch die Interessen des Vermieters nicht zu rechtfertigen wäre. Bei der Festlegung der Art und Dauer der gewährten Erstreckung steht dem Gericht innerhalb des gesetzlichen Rahmens ein weiter Ermessensspielraum zu (<ref-ruling> E. 4b S. 230; Urteil 4A_368/2017 vom 19. Februar 2018 E. 7.1 mit Hinweis). Derartige Ermessensentscheide überprüft das Bundesgericht mit Zurückhaltung und greift nur ein, wenn die Vorinstanz grundlos von in Lehre und Rechtsprechung anerkannten Grundsätzen abgegangen ist, wenn sie Tatsachen berücksichtigt hat, die für den Entscheid im Einzelfall keine Rolle hätten spielen dürfen, oder wenn sie umgekehrt Umstände ausser Betracht gelassen hat, die hätten beachtet werden müssen. Es greift ausserdem in Ermessensentscheide ein, wenn sich diese als offensichtlich unbillig, als in stossender Weise ungerecht erweisen (<ref-ruling> E. 5.3.2 S. 345; <ref-ruling> E. 2 S. 123 f.).
4.3. Die Vorinstanz erwog, die Erstinstanz habe die lange Mietdauer mittelbar über die Ortsverbundenheit und über die Ortsgebundenheit berücksichtigt. Über die Ortsverbundenheit insbesondere, indem sie angenommen habe, die Kündigung verlange eine grosse Umstellung, aber auch, indem sie davon ausgegangen sei, die Beschwerdeführer seien zur Aufrechterhaltung sozialer Kontakte auf gute Verbindungen in ihr jetziges Wohnquartier angewiesen, weshalb sie auf eine Wohnung innerhalb der Stadt Zürich angewiesen seien. Die Ortsgebundenheit sei ebenso Ausfluss der langen Mietdauer. Aufgrund der langen Mietdauer habe die Beschwerdeführerin 1 ihr "medizinisches Umfeld" im Laufe der Jahre innerhalb der Stadt Zürich aufgebaut.
4.4. Entgegen den Beschwerdeführern hat die Vorinstanz damit - wie bereits die Erstinstanz - die lange Mietdauer durchaus berücksichtigt, und zwar mittelbar im Rahmen der Prüfung der Kriterien der Ortsverbundenheit und der Ortsgebundenheit. Dass die Vorinstanz mit der Erstinstanz eine quartierbezogene Ortsgebundenheit aufgrund des Umstands der durch öffentliche Verkehrsmittel sehr gut erschlossenen Stadt Zürich verneinte, ändert diesbezüglich nichts. Dass nach Ansicht der Beschwerdeführer die lange Mietdauer für sich allein noch stärker zu berücksichtigen gewesen wäre, erfordert es jedenfalls nicht, in den ausführlich und nachvollziehbar begründeten Ermessensentscheid der Vorinstanz einzugreifen (vgl. hiervor E. 4.2). Etwas anderes ergibt sich - entgegen den Beschwerdeführern - auch nicht aus dem Urteil 4A_130/2008 vom 26. Mai 2008. Im Übrigen wäre vorliegend ohnehin zu berücksichtigen, dass die Beschwerdeführer bereits eine faktisch längere Erstreckung erhalten haben, weil das bundesgerichtliche Verfahren über die von den Vorinstanzen gewährte Erstreckung hinaus andauerte und der Beschwerde antragsgemäss die aufschiebende Wirkung erteilt wurde.
5.
Nach dem Ausgeführten ist die Beschwerde abzuweisen, soweit überhaupt darauf eingetreten werden kann. Dem Ausgang des Verfahrens entsprechend werden die Beschwerdeführer unter solidarischer Haftbarkeit kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und 5, Art. 68 Abs. 1, 2 und 4 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 4'000.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3.
Die Beschwerdeführer haben unter solidarischer Haftbarkeit die Beschwerdegegnerin für das bundesgerichtliche Verfahren 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, 16. Januar 2020
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Gross