Faits :
A.
C._ est propriétaire de la parcelle n° 259, feuille 22 de la commune de Cologny. D'une surface de 2113 m 2, la parcelle est colloquée en 5 ème zone, dite zone villa (cf. art. 58 ss de la loi genevoise sur les constructions et les installations diverses [LCI]; RS/GE L 5 05), ainsi que simultanément dans la zone de protection des rives du lac au sens de la loi genevoise sur la protection générale des rives du lac (LPRLac; RS/GE L 4 10). Sur la parcelle, qui se trouve en pente, est bâtie une villa comportant un logement d'une surface au sol de 328 m 2. Elle est bordée, dans sa partie haute, par le chemin Byron, qui est lui-même en pente.
B.
Le 13 octobre 2014, C._ a déposé une demande d'autorisation de construire auprès du Département de l'aménagement, du logement et de l'énergie (devenu depuis lors le Département du territoire). Le projet prévoyait la construction de deux villas contiguës avec piscines, vérandas et couverts à voitures, après démolition de la villa existante.
Lors de l'instruction effectuée par le Département, le projet a fait l'objet, le 13 novembre 2014, d'un préavis défavorable de la commune de Cologny. Pour sa part, le 13 janvier 2015, la Commission des monuments, de la nature et des sites (CMNS), soit pour elle la Sous-commission nature et sites (SCNS), a préavisé favorablement le projet, sous condition.
Par décision du 21 mai 2015, le Département a accordé l'autorisation sollicitée.
C.
A.A_ et B.A._, propriétaires de la parcelle voisine n° 258, ont formé un recours contre cette décision auprès du Tribunal administratif de première instance. Après que la cause avait été suspendue sur requête commune des parties pendant près de deux ans, le Tribunal administratif a rejeté le recours par jugement du 12 octobre 2017.
Par arrêt du 20 novembre 2018, la Chambre administrative de la Cour de justice genevoise a rejeté le recours formé par A.A_ et B.A._ contre le jugement du 12 octobre 2017.
D.
A.A_ et B.A._ forment un recours en matière de droit public contre l'arrêt du 20 novembre 2018. Ils concluent, avec suite de frais et dépens, à sa réforme en ce sens que l'autorisation de construire n'est pas accordée.
Invitée à se déterminer sur le recours, la cour cantonale a renoncé à présenter des observations, se référant aux considérants de l'arrêt entrepris. Le Département du territoire a conclu au rejet du recours dans la mesure de sa recevabilité. Quant à C._, elle a conclu, avec suite de frais et dépens, au rejet du recours.
A.A_ et B.A._, de même que C._, ont par la suite persisté dans leurs conclusions respectives.

Considérant en droit :
1.
1.1. Dirigé contre une décision finale (<ref-law>) prise en dernière instance cantonale (art. 86 al. 1 let. d LTF) dans le domaine du droit public des constructions (<ref-law>), le recours est recevable comme recours en matière de droit public, aucune des exceptions prévues à l'<ref-law> n'étant réalisée.
1.2. En vertu de l'<ref-law>, peut former un recours en matière de droit public quiconque a pris part à la procédure devant l'autorité précédente ou a été privé de la possibilité de le faire (let. a), est particulièrement atteint par la décision ou l'acte normatif attaqué (let. b) et a un intérêt digne de protection à son annulation ou à sa modification (let. c).
Selon la jurisprudence, le voisin a qualité pour agir lorsque son terrain jouxte celui du constructeur ou se trouve à proximité immédiate de celui-ci (<ref-ruling> consid. 2b p. 174; <ref-ruling> consid. 5c p. 511). La distance par rapport à l'objet du litige ne constitue toutefois pas l'unique critère pour déterminer la qualité pour agir du voisin. S'il est certain ou très vraisemblable que l'installation litigieuse sera à l'origine d'immissions - bruit, vibrations, lumières ou autres - touchant spécialement les voisins, même situés à quelque distance, ces derniers peuvent avoir qualité pour recourir (<ref-ruling> consid. 2.3.1 p. 285; arrêt 1C_654/2017 du 3 octobre 2018 consid. 2.2; arrêt 1C_565/2012 du 23 janvier 2013 consid. 2.1 in SJ 2013 I 526). Le voisin doit en outre retirer un avantage pratique de l'annulation ou de la modification de la décision contestée qui permette d'admettre qu'il est touché dans un intérêt personnel se distinguant nettement de l'intérêt général des autres habitants de la collectivité concernée de manière à exclure l'action populaire; il doit ainsi invoquer des dispositions du droit public des constructions susceptibles d'avoir une incidence sur sa situation de fait ou de droit (<ref-ruling> consid. 2.2.3 et 2.3 p. 33 s.; <ref-ruling> consid. 1.3.1 s. p. 252 s.).
En l'espèce, les recourants ont pris part à la procédure de recours devant la Cour de justice. Ils sont particulièrement touchés par l'arrêt cantonal qui confirme le projet de construction sis sur la parcelle directement voisine de la leur. Ils se prévalent en outre de prescriptions de droit des constructions relatives à la hauteur maximale des bâtiments et prétendent qu'ils seraient fortement atteints par les constructions projetées, qui surplomberaient leur parcelle et leur ôteraient toute intimité. Ils disposent ainsi de la qualité pour recourir en vertu de l'<ref-law>.
1.3. Les autres conditions de recevabilité du recours sont réunies si bien qu'il y a lieu d'entrer en matière.
2.
Les recourants se plaignent d'une application arbitraire de l'art. 7 al. 1 LPRLac relatif au nombre de niveaux autorisé dans les zones de protection des rives du lac.
2.1.
2.1.1. Le Tribunal fédéral ne revoit l'interprétation et l'application du droit cantonal et communal que sous l'angle de l'arbitraire. Une décision est arbitraire lorsqu'elle viole gravement une norme ou un principe juridique clair et indiscuté, ou lorsqu'elle contredit d'une manière choquante le sentiment de la justice et de l'équité. Le Tribunal fédéral n'a pas à déterminer quelle est l'interprétation correcte que l'autorité cantonale aurait dû donner des dispositions applicables; il doit uniquement examiner si l'interprétation qui a été faite est défendable. Par conséquent, si celle-ci ne se révèle pas déraisonnable ou manifestement contraire au sens et au but de la disposition ou de la législation cantonale en cause, elle sera confirmée, même si une autre solution paraît également concevable, voire préférable. De plus, il ne suffit pas que les motifs de la décision attaquée soient insoutenables, encore faut-il que cette dernière soit arbitraire dans son résultat (<ref-ruling> consid. 5.4 p. 327; <ref-ruling> consid. 4.1 p. 566; <ref-ruling> consid. 4.3 p. 319). Dans ce contexte, la partie recourante est soumise aux exigences accrues de motivation de l'<ref-law>.
2.1.2. La LPRLac vise à protéger les rives du lac Léman et les zones sensibles voisines (cf. art. 1 al. 1 LPRLac), en instaurant un certain nombre de restrictions aux constructions pouvant être érigées dans le périmètre à protéger. Ainsi notamment, les constructions situées en 5 ème zone ne peuvent en principe comporter que deux niveaux avec toiture plate ou un niveau avec toiture habitable, le nombre de niveaux étant déterminé sur la façade côté lac (art. 7 al. 1 LPRLac).
Aux termes de l'art. 13 al. 1 LPRLac, si les circonstances le justifient et que cette mesure ne porte pas atteinte au but général poursuivi par la loi, le département peut déroger aux art. 6 à 11 LPRLac. Dans ce cadre, les requêtes en autorisation de construire font l'objet d'un préavis de la commune concernée, de la CMNS, et le cas échéant de la direction générale de l'agriculture et de la nature ainsi que de la commission consultative de la diversité biologique (art. 13 al. 2 LPRLac).
2.1.3. S'agissant des constructions comprises dans la 5 ème zone, l'art. 58 al. 1 LCI prévoit que celles-ci sont érigées en ordre contigu ou non contigu. Est réputée en ordre contigu, l'édification de deux maisons au moins, réunies par un mur mitoyen ou par une construction de peu d'importance et disposant chacun de son propre accès de plain-pied (art. 58 al. 2 LCI).
2.2. En l'espèce, la cour cantonale a estimé que le Département n'avait pas abusé de son pouvoir d'appréciation en accordant une dérogation au nombre de niveaux, comme le permettait l'art. 13 al. 1 et 2 LPRLac, laquelle dérogation portait sur l'édicule, d'une surface de 23 m2, formant l'entrée de la villa située en amont.
Pour le reste, si la commune de Cologny avait certes préavisé défavorablement le projet au motif de l'impact important sur le côté lac, la façade nord-ouest présentant cinq niveaux construits superposés, la cour cantonale a néanmoins estimé que, s'agissant de deux constructions distinctes comprenant chacune deux niveaux habitables, il ne se justifiait pas d'additionner ces différents niveaux, de sorte que, dans cette mesure, le projet était conforme au prescrit de l'art. 7 al. 1 LPRLac (cf. arrêt entrepris, consid. 6 p. 10).
2.3. Les recourants contestent que le projet porte sur deux constructions distinctes. Ils se prévalent à cet égard des plans produits au dossier, dont en particulier d'un plan en coupe ainsi que d'un plan de la façade vue du côté lac qui feraient apparaître une construction présentant cinq niveaux et qui dénoteraient donc une violation flagrante de l'art. 7 al. 1 LPRLac.
Cela étant, quoi qu'en disent les recourants, les plans produits par l'intimée à l'appui de sa demande d'autorisation de construire figurent bien deux habitations indépendantes construites sur un terrain en pente, disposant chacune de son propre accès et reliées entre elles par un couvert à voitures. Dans cette mesure, il n'y a rien d'arbitraire à les assimiler à des constructions contiguës au sens de l'art. 58 al. 2 LCI et partant distinctes l'une de l'autre. Ainsi, quand bien même leur positionnement parallèle - l'une en amont, l'autre en aval du terrain en pente - pourrait donner l'impression que les villas se superposent pour ne former qu'un seul bâtiment, on ne voit pas que l'art. 7 al. 1 LPRLac impose dans cette configuration d'additionner les niveaux de chacune des constructions.
De surcroît, on relève que, dans son préavis favorable sous condition du 13 janvier 2015, la CMNS paraît avoir tenu compte de l'impact visuel du projet en imposant la mise en place d'une toiture végétalisée extensive. La Commission considérait du reste que les constructions projetées allaient donner lieu à une diminution générale de l'impact en comparaison avec l'immeuble existant (cf. arrêt entrepris, p. 3).
Il n'apparaît pas dans ce contexte que l'objectif de protection visé par la LPRLac serait vidé de sa substance, ni que l'art. 7 al. 1 LPRLac aurait été appliqué de manière arbitraire. Le grief est dès lors infondé.
2.4. Pour le surplus, les recourants ne contestent pas, au regard de l'art. 13 LPRLac, l'octroi d'une dérogation portant sur l'édicule d'entrée.
3.
Il s'ensuit que le recours doit être rejeté. Les frais judiciaires sont mis à la charge des recourants, débiteurs solidaires (art. 66 al. 1 et 5 LTF). Ces derniers, solidairement entre eux, verseront en outre des dépens à l'intimée C._, qui a obtenu gain de cause avec l'assistance de son avocat Me Guy Zwahlen (art. 68 al. 1 et 4 LTF). Le Département, qui a agi dans le cadre de ses attributions officielles, n'a en revanche pas droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 4000 fr., sont mis à la charge des recourants, solidairement entre eux.
3.
Une indemnité de 3000 fr. est allouée à l'intimée, à la charge solidaire des recourants.
4.
Le présent arrêt est communiqué aux mandataires des parties, au Département du territoire de la République et canton de Genève et à la Cour de justice de la République et canton de Genève, Chambre administrative.
Lausanne, le 11 novembre 2019
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Chaix
Le Greffier : Tinguely