Sachverhalt:
A.
Die Bausektion des Stadtrates von Zürich verweigerte am 21. Oktober 2014 G._ die nachträgliche Erteilung einer baurechtlichen Bewilligung für die sexgewerbliche Nutzung des Erdgeschosses der Liegenschaft an der I._-Strasse in Zürich (Kat.-Nr. xxx). Weil die Räumlichkeiten aber seit 21 Jahren ununterbrochen zu sexgewerblichen Zwecken genutzt worden seien und die Sittenpolizei davon Kenntnis gehabt habe, verzichtete die Bausektion auf die Wiederherstellung des rechtmässigen Zustands und versah den Bauentscheid mit verschiedenen Auflagen.
B.
Den gegen diesen Entscheid von den Nachbarn A._, B._, C._, D._, E._ und F._ erhobenen Rekurs wies das Baurekursgericht mit Entscheid vom 27. November 2015 ab. Auch die dagegen erhobene Beschwerde blieb erfolglos: Das Verwaltungsgericht wies ihr Rechtsmittel mit Urteil vom 16. Juni 2016 ab.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 9. September 2016 gelangen A._ und die weiteren im Rubrum aufgeführten Nachbarn an das Bundesgericht und beantragen, das Urteil des Verwaltungsgericht sei aufzuheben und die Sache sei zur Neuentscheidung an die Vorinstanz zurückzuweisen. Eventuell sei der Entscheid der Bausektion insoweit aufzuheben, als auf die Wiederherstellung des rechtmässigen Zustands verzichtet werde, und die Bausektion sei einzuladen, einen Wiederherstellungsbefehl zu verfügen.
Das Verwaltungsgericht schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Bausektion beantragt, die Beschwerde sei abzuweisen und der Stadt Zürich seien im Falle des Unterliegens keine Gerichtskosten aufzuerlegen. G._ (Beschwerdegegnerin) schliesst ebenfalls auf Abweisung der Beschwerde. H._ hat sich nicht vernehmen lassen. Die Beschwerdeführer halten in der Replik an ihren Anträgen fest.

Erwägungen:
1.
1.1. Angefochten ist ein Endentscheid (<ref-law>) in einer Angelegenheit des öffentlichen Rechts, die nicht unter den Ausnahmekatalog von <ref-law> fällt, weshalb die Beschwerde in öffentlich-rechtlichen Angelegenheiten grundsätzlich offen steht (<ref-law>).
1.2. Gemäss <ref-law> ist zur Beschwerde in öffentlich-rechtlichen Angelegenheiten berechtigt, wer vor der Vorinstanz am Verfahren teilgenommen hat oder keine Möglichkeit zur Teilnahme erhalten hatte (lit. a), durch den angefochtenen Entscheid besonders berührt ist (lit. b) und ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung hat (lit. c). Verlangt wird somit neben der formellen Beschwer, dass die Beschwerdeführer über eine spezifische Beziehungsnähe zur Streitsache verfügen und einen praktischen Nutzen aus der Aufhebung oder Änderung des angefochtenen Entscheids ziehen. Die Nähe der Beziehung zum Streitgegenstand muss bei Bauprojekten insbesondere in räumlicher Hinsicht gegeben sein (<ref-ruling> E. 2.1 S. 52 mit Hinweis). Diese Voraussetzungen sind bei den Beschwerdeführern erfüllt: Als direkte Nachbarn der Liegenschaft an der I._-Strasse stehen sie in einer hinreichend engen räumlichen Beziehung zum streitbetroffenen Betrieb. Da davon allenfalls störende Immissionen ausgehen könnten und die Beschwerdeführer mit ihren Rechtsbegehren vor der Vorinstanz nicht durchgedrungen sind, haben sie ein berechtigtes Interesse an der Überprüfung des angefochtenen Entscheids durch das Bundesgericht. Dasselbe gilt, soweit die Vorinstanz ihre Vorbringen materiell nicht behandelt hat.
1.3. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann insbesondere die Verletzung von Bundesrecht gerügt werden (<ref-law>). Dieses wendet das Bundesgericht grundsätzlich von Amtes wegen an (<ref-law>). Die Verletzung von Grundrechten - einschliesslich die willkürliche Anwendung von kantonalem Recht - wird vom Bundesgericht aber nur insoweit geprüft, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>). Hierzu gelten qualifizierte Begründungsanforderungen: Das Bundesgericht prüft nur klar und detailliert erhobene und, soweit möglich, belegte Rügen (<ref-ruling> E. 2.2 S. 232; <ref-ruling> E. 1.4.2 S. 254 f.; je mit Hinweisen).
Soweit die Beschwerdeführer eine Verletzung der Eigentumsgarantie und der in Art. 3 der Raumplanungsverordnung (RPV; SR 700.1) vorgeschriebenen Interessenabwägung geltend machen, legen sie nicht in rechtsgenüglicher Weise dar, worin diese bestehen soll. Auf die Beschwerde ist in diesem Umfang nicht einzutreten. Dasselbe gilt insoweit, als sich die Beschwerde gegen Entscheide der Vorinstanzen des Verwaltungsgerichts richtet. Diese sind im Rahmen des Streitgegenstands durch dessen Urteil ersetzt worden (Devolutiveffekt) und gelten als inhaltlich mitangefochten (<ref-ruling> E. 1.4 S. 144).
2.
2.1. Die Beschwerdeführer erblicken in der Weigerung der Vorinstanz, ihre Rüge zu prüfen, wonach die Voraussetzungen des Vertrauensschutzes für eine Nutzung der Räumlichkeiten zu sexgewerblichen Zwecken nicht erfüllt seien, eine (formelle) Rechtsverweigerung und eine Verletzung des rechtlichen Gehörs. Zur Begründung führen sie im Wesentlichen an, das Verwaltungsgericht verkenne, dass beschwerdeberechtigte Nachbarn sämtliche Rügen erheben dürften, die ihnen bei einer Gutheissung des Rechtsmittels durch die Aufhebung des angefochtenen Entscheids einen praktischen Nutzen verschaffen könnten. Ihr Vorbringen, wonach eine verkürzte Verwirkungsfrist aus Gründen des Vertrauensschutzes nicht angenommen werden dürfe, sei geeignet, das angestrebte Ziel - nämlich die Wiederherstellung des rechtmässigen Zustands - zu erreichen.
2.2. Die Beschwerdeführer stützen sich insbesondere auf das kantonale Verfahrensrecht ab und rügen dessen willkürliche Anwendung. Dies ist insofern zu präzisieren, als gemäss <ref-law> die Legitimation und die Beschwerdegründe im kantonalen Verfahren mindestens so weit gefasst sein müssen wie vor Bundesgericht (vgl. auch Art. 33 Abs. 3 lit. a RPG [SR 700]). Aus diesen Bestimmungen ergibt sich, dass die kantonalen Behörden die Rechtsmittelbefugnis nicht enger fassen dürfen, als dies für die Beschwerde an das Bundesgericht vorgesehen ist. Gemäss <ref-law> muss die unmittelbare Vorinstanz des Bundesgerichts mindestens die Rügen nach den Art. 95-98 BGG prüfen können. Diese Bestimmung verankert unter der Marginalie "Einheit des Verfahrens" den Grundsatz, wonach die Kognition des oberen kantonalen Gerichts nicht enger sein darf als jene des Bundesgerichts. Daraus ergibt sich, dass sich die kantonalen Behörden mindestens mit denjenigen Rügen auseinandersetzen müssen, welche vor Bundesgericht geltend gemacht werden können (vgl. <ref-ruling> E. 2.2 S. 53; Urteil 1D_1/2015 vom 1. Juli 2015 E. 2.3).
2.3. Das Verwaltungsgericht erwog im angefochtenen Entscheid, die Beschwerdeführer seien als unmittelbare Nachbarn der streitbetroffenen Liegenschaft zwar grundsätzlich zur Beschwerde legitimiert. Sie könnten sich aber nicht darauf berufen, die Voraussetzungen des Vertrauensschutzes für eine Nutzung der Räumlichkeiten zu sexgewerblichen Zwecken seien nicht erfüllt. Der Vertrauensschutz sei von der Art und Weise seiner konzeptionellen Ausgestaltung darauf ausgerichtet, den von einer behördlichen Anordnung direkt betroffenen Bauherrn gegenüber dem Staat zu schützen, nicht aber Drittpersonen.
2.4. Dieser Argumentation kann nicht gefolgt werden. Mit ihrer rügespezifischen Beurteilung vermengt die Vorinstanz Rechtsmittelbefugnis und Beschwerdegründe. Die Beschwerdelegitimation richtet sich ausschliesslich nach <ref-law>. Sind dessen Voraussetzungen wie hier erfüllt (vgl. E. 1.2 hiervor), sind die Beschwerdeführer mit sämtlichen der in <ref-law> aufgeführten Rügen zum Verfahren zuzulassen (<ref-ruling> E. 6.4 S. 314; <ref-ruling> E. 2.3 S. 34). Die Beschwerdeführer können daher die Überprüfung eines Bauvorhabens im Lichte all jener Rechtssätze verlangen, die sich rechtlich oder tatsächlich im dem Sinne auf ihre Stellung auswirken, dass ihnen im Falle des Obsiegens ein praktischer Nutzen entsteht (<ref-ruling> E. 2.1 S. 52).
2.5. Nach der bundesgerichtlichen Rechtsprechung verwirkt der Anspruch der Behörden auf Wiederherstellung des rechtmässigen Zustands im Interesse der Rechtssicherheit grundsätzlich nach 30 Jahren (<ref-ruling> E. 8 S. 367 mit Hinweisen). Den Kantonen steht es frei, kürzere Verwirkungsfristen vorzusehen (vgl. Urteil 1P.768/2000 vom 19. September 2001 E. 5b, in: ZBl 103/2002 S. 188). Solche kürzeren Verwirkungsfristen können sich zudem aus Gründen des Vertrauensschutzes ergeben (<ref-ruling> E. 7 S. 365). Dies kann namentlich der Fall sein, wenn die Behörden den baurechtswidrigen Zustand über Jahre hinaus duldeten, obwohl ihnen die Gesetzeswidrigkeit bekannt war oder sie diese bei Anwendung der gebotenen Sorgfalt hätten kennen müssen. Nach ständiger Rechtsprechung kann sich darauf aber nur berufen, wer selbst im guten Glauben gehandelt hat, d.h. angenommen hat und (unter Anwendung zumutbarer Sorgfalt) annehmen durfte, die von ihm ausgeübte Nutzung sei rechtmässig bzw. stehe mit der Baubewilligung in Einklang (<ref-ruling> E. 7.1 S. 365; <ref-ruling> E. 6 S. 35; je mit Hinweisen).
2.6. Da sich die Rüge der Beschwerdeführer, der Anspruch der Stadt Zürich auf Wiederherstellung des rechtmässigen Zustands sei aus Gründen des Vertrauensschutzes (noch) nicht untergegangen, auf Bundesrecht stützt (<ref-law>) und geeignet ist, ihnen bei einem Obsiegen einen praktischen Nutzen im Sinne der Beseitigung der von der sexgewerblichen Nutzung der Räumlichkeiten ausgehenden Immissionen zu verschaffen, hätte das Verwaltungsgericht dieses Vorbringen materiell prüfen müssen. Gewiss ist der Vertrauensschutz "von der Art und Weise seiner konzeptionellen Ausgestaltung darauf ausgerichtet, den von einer behördlichen Anordnung direkt betroffenen Bauherrn gegenüber dem Staat zu schützen", wie die Vorinstanz ausführt. Das schliesst aber nicht aus, dass Drittpersonen in eigenen, schutzwürdigen Interessen betroffen werden können, wenn eine staatliche Behörde das Vorliegen eines Vertrauenstatbestands bejaht, was gerade in den - von der Vorinstanz ebenfalls diskutierten und hier vorliegenden - Konstellationen des Vertrauensschutzes zulasten Dritter zutrifft (vgl. dazu BEATRICE WEBER-DÜRLER, Vertrauensschutz im öffentlichen Recht, S. 146 ff.). In solchen Fällen sind die Dritten zur Rüge befugt, die Voraussetzungen des Vertrauensschutzes seien nicht gegeben oder die Abwägung der einander entgegenstehenden Interessen sei fehlerhaft erfolgt (dazu WEBER-DÜRLER, a.a.O., S. 148 ff.). Ebenso hätte sich das Verwaltungsgericht mit den für die Anordnung eines Wiederherstellungsbefehls massgebenden allgemeinen verfassungs- und verwaltungsrechtlichen Prinzipien auseinandersetzen müssen, zu denen namentlich die in <ref-law> festgehaltenen Grundsätze der Verhältnismässigkeit und des Schutzes des guten Glaubens gehören (BGE <ref-ruling> E. 6 S. 35). Das Verwaltungsgericht ist aufgrund seiner Kognition zu einer Rechtskontrolle verpflichtet (§ 50 Abs. 1 i.V.m. § 20 Abs. 1 lit. a und b des Verwaltungsgerichtsgesetz des Kantons Zürich [VRG; LS 175.2]). Diese erstreckt sich auf jegliche Verletzung einer Rechtsnorm, mithin auf Bestimmungen des kantonalen Rechts und des Bundesrechts.
Die Vorinstanz hat somit gegen das Verbot der formellen Rechtsverweigerung im Sinne von <ref-law> und gegen den Anspruch auf rechtliches Gehör gemäss <ref-law> verstossen. Die Beschwerde erweist sich in diesem Punkt als begründet. Aufgrund der formellen Natur der festgestellten Verstösse ist der angefochtene Entscheid unabhängig von deren Einfluss auf den Verfahrensausgang aufzuheben (<ref-ruling> E. 5.4 S. 70; 99 E. 3.8 S. 106). Die Sache ist zu neuem Entscheid an die Vorinstanz zurückzuweisen. Im Rahmen der (Neu-) Beurteilung wird sich das Verwaltungsgericht auch zur geltend gemachten Gehörsverletzung durch das Baurekursgericht hinsichtlich der Dauer der Verwirkungsfrist äussern und den Einwand prüfen müssen, wonach die Wiederherstellung aufgrund überwiegender öffentlicher Interessen geboten sei.
3.
3.1. Die Beschwerdeführer bringen ferner vor, das Verwaltungsgericht habe den Sachverhalt offensichtlich unrichtig festgestellt und die Beweise willkürlich gewürdigt, wenn es folgerte, aus den Akten ergäben sich keine Hinweise auf eine erhebliche Intensivierung der sexgewerblichen Nutzung der Räumlichkeiten. Dabei übersehen sie aber, dass die Vorinstanz in diesem Zusammenhang erwog, die Beschwerdeführer hätten sich mit den einschlägigen Erwägungen des Baurekursgerichts nicht genügend substanziiert auseinandergesetzt, sondern lediglich wiederholt, was sie bereits in ihrer Rekursschrift vorgebracht hätten. Der Streitgegenstand vor Bundesgericht beschränkt sich daher auf die Frage, ob die Beschwerdeführer ihre Verwaltungsgerichtsbeschwerde rechtsgenüglich begründet haben bzw. ob das Verwaltungsgericht diesbezüglich zu hohe Anforderungen an das kantonale Rechtsmittel gestellt hat.
3.2. Gemäss <ref-law> muss mindestens eine gerichtliche Instanz im Kanton das Recht von Amtes wegen anwenden. Hier hat das zürcherische Verwaltungsgericht als zweite gerichtliche Instanz im Kanton entschieden. Zuvor hatte sich das Baurekursgericht, das über eine umfassende Kognition verfügt (§ 20 Abs. 1 VRG; vgl. ferner Art. 33 Abs. 3 lit. b RPG), zu den in der Rekursschrift vorgebrachten Einwänden geäussert. Da bereits dieses trotz der Rechtsanwendung von Amtes wegen nicht verpflichtet ist, wie eine erstinstanzliche Behörde alle möglicherweise relevanten Rechtsfragen aufzugreifen, sondern sich grundsätzlich darauf beschränken kann, sich mit den Argumentationen der Parteien auseinanderzusetzen (<ref-ruling> E. 6.5 S. 314 mit Hinweisen), muss dies umso mehr für das Verwaltungsgericht als letzte kantonale Instanz gelten (vgl. dazu DANIELA THURNHERR, in: Fachhandbuch Öffentliches Baurecht, 2016, S. 709). Dieses verstiess nicht gegen Bundesrecht, wenn es mangels ausreichender Substanziierung das Vorbringen zur Nutzungsintensivierung materiell nicht behandelt hat, nachdem sich bereits das Baurekursgericht damit auseinandergesetzt hatte. Die Beschwerdeführer zeigen in ihrer Rechtsschrift denn auch nicht auf, inwiefern sie den Begründungsanforderungen nachgekommen sein sollen. Zwar zitieren sie eine längere Passage aus ihrer Verwaltungsgerichtsbeschwerde, in der sie sich auf einen Polizeirapport als Beleg für die Nutzungsintensivierung berufen. Zu diesem hat sich aber bereits das Baurekursgericht geäussert und erwogen, er lege nicht nahe, dass im Vergleich zu früher mehr Prostituierte in den fraglichen Räumlichkeiten arbeiteten (vgl. Entscheid vom 27. November 2015 E. 4.3). Unter diesen Umständen ist nicht zu beanstanden, wenn die Vorinstanz in ihrem Verfahren auf das nämliche Argument nicht noch einmal eingegangen ist.
4.
Nach dem Gesagten ist die Beschwerde teilweise gutzuheissen, soweit darauf einzutreten ist. Der angefochtene Entscheid ist aufzuheben und die Angelegenheit an das Verwaltungsgericht zurückzuweisen, damit dieses die Begründetheit des Vorbringens prüft, wonach der Vertrauensschutz der Wiederherstellung des rechtmässigen Zustands nicht entgegenstehe. Im Übrigen ist die Beschwerde abzuweisen.
Bei diesem Verfahrensausgang obsiegen die Beschwerdeführer im Wesentlichen, weshalb die private Beschwerdegegnerin kostenpflichtig würde (<ref-law>) und den anwaltlich vertretenen Beschwerdeführern eine Parteientschädigung auszurichten hätte (Art. 68 Abs. 1 und 2 BGG). Unnötige Kosten hat indessen zu bezahlen, wer sie verursacht (Art. 66 Abs. 3 und Art. 68 Abs. 4 BGG). Vorliegend hat das Verwaltungsgericht gegen das Verbot der formellen Rechtsverweigerung und den Anspruch auf rechtliches Gehör verstossen. Es rechtfertigt sich daher, auf die Erhebung von Kosten zu verzichten und den Kanton Zürich zu verpflichten, den Beschwerdeführern für das bundesgerichtliche Verfahren eine angemessene Entschädigung auszurichten.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen, soweit darauf einzutreten ist, und das Urteil des Verwaltungsgerichts des Kantons Zürich vom 16. Juni 2016 wird aufgehoben. Die Angelegenheit wird zur weiteren Behandlung im Sinne der Erwägungen an die Vorinstanz zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Zürich hat die Vertreterin der Beschwerdeführer, Rechtsanwältin Nadja Herz, für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, der Bausektion der Stadt Zürich, H._ und dem Verwaltungsgericht des Kantons Zürich, 1. Abteilung, schriftlich mitgeteilt.
Lausanne, 1. Dezember 2016
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Die Gerichtsschreiberin: Pedretti