Faits : A. La société G._ SA, actuellement en liquidation (ci-après : G._ SA), est propriétaire de l'immeuble sis Grand-Rue 16 - rue du Cheval Blanc 2, sur la parcelle n° 4'901, feuille 26 de la commune de Genève-Cité, également dénommé "Maison Vautrain". Ainsi qu'il résulte de l'état locatif du 23 mars 2009, cet immeuble compte actuellement un local au sous-sol, deux arcades commerciales au rez-de-chaussée, un commerce au premier étage, deux bureaux à usage commercial (un au premier étage et l'autre au quatrième), ainsi que dix-sept appartements, du premier au quatrième étage (pour trente-quatre pièces). Le nombre de pièces moyen par logement est de deux. Le bâtiment est fortement dégradé, voire insalubre par endroits. Le 10 juin 2009, G._ SA a déposé une demande d'autorisation de construire en vue de la rénovation de l'immeuble en question, ainsi que de la mise en place d'un ascenseur et de la transformation des appartements. Le projet faisait passer le nombre d'appartements de quinze à six. Dans le cadre de l'instruction de la demande, la Commission des monuments, de la nature et les sites (ci-après : la CMNS) a procédé à plusieurs visites de l'immeuble pour constater sa valeur historique et désigner les éléments dignes de protection qui devaient être maintenus. Des préavis favorables (ou favorables sous conditions) ont été émis par la Direction générale de l'aménagement du territoire, la Direction générale de l'eau, le Service de l'énergie, la Police du feu, la Ville de Genève, le Service juridique LDTR, le Service "sécurité locataires", la CMNS et le Service des monuments et des sites. Par décision du 17 janvier 2013, le Département des constructions et des technologies de l'information du canton de Genève (devenu depuis le 11 décembre 2013 le Département de l'aménagement, du logement et de l'énergie) a octroyé l'autorisation sollicitée; l'autorisation prévoyait que les conditions figurant dans les préavis du Service des monuments et des sites, de la Ville de Genève, du Service "sécurité locataires", du Service de l'énergie et de la Direction générale de l'eau devaient être respectées et faisaient partie intégrante de l'autorisation; conformément à l'état locatif futur, les surfaces commerciales seraient regroupées au rez-de-chaussée et au premier étage, les autres niveaux étant réservés à l'habitation; les travaux de transformation nécessitant le départ des locataires, l'ouverture du chantier était subordonnée à leur relogement à satisfaction. B. A._, B._, C._, D._, E._, F._ (ci-après: A._ et consorts), locataires de cet immeuble, ont recouru contre l'autorisation du 17 janvier 2013 auprès du Tribunal administratif de première instance du canton de Genève (ci-après: le TAPI). Après avoir procédé à une audience de comparution personnelle des parties, le TAPI a rejeté le recours, par jugement du 19 novembre 2013. Dans l'intervalle, par arrêté du 30 octobre 2013, le Conseil d'Etat du canton de Genève a déclaré le bâtiment litigieux, monument classé. Les éléments à conserver désignés par le Service des monuments et des sites dans sa liste du 15 décembre 2011 devaient être intégrés dans l'objectif de protection recherché. C. A._ et consorts ont interjeté un recours contre le jugement du 19 novembre 2013 auprès de la Chambre administrative de la Cour de justice du canton de Genève (ci-après: le Cour de justice). Après avoir procédé à une inspection locale en présence des parties et d'une commissaire de la CMNS le 4 novembre 2014, la Cour de justice a rejeté le recours, par arrêt du 3 mai 2016. D. Agissant par la voie du recours en matière de droit public, A._ et consorts demandent principalement au Tribunal fédéral d'annuler l'arrêt du 3 mai 2016 et de déclarer nulle l'autorisation de construire du 17 janvier 2013. Ils concluent subsidiairement au renvoi de la cause à l'instance précédente pour complément d'instruction et nouvelle décision au sens des considérants. La Cour de justice renonce à se déterminer et persiste dans les considérants et le dispositif de son arrêt. G._ SA conclut principalement au rejet du recours et subsidiairement à la fixation du loyer après travaux de la pièce créée dans les combles à 3'405 francs par an et au renvoi de la cause au service LDTR afin qu'il modifie l'état locatif en conséquence. Le Département de l'aménagement, du logement et de l'énergie conclut aussi au rejet du recours. Un second échange d'écritures a eu lieu, au terme duquel les parties ont maintenu leurs conclusions respectives. Les recourants se sont encore déterminés par courrier du 14 novembre 2016. E. Par ordonnance du 12 juillet 2016, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif formée par les recourants.