Faits: A. La société K._ SA est propriétaire de la parcelle n° 12'640 de la commune de Montreux, sise à M._. D'une surface de 904 m2, ce bien-fonds supporte une maison de maître (ECA n° 4'014) d'une surface au sol de 273 m2, qui a été dans une large mesure démolie. La parcelle n° 12'640 et la parcelle contiguë n° 1'078 sont issues d'un fractionnement de la parcelle d'origine n° 1'078 (d'une surface initiale de 3'694 m2) qui a fait l'objet le 7 septembre 2011 d'une mention au registre foncier, à savoir une "restriction LATC" selon laquelle "l'ensemble des deux biens-fonds 1'078 et 12'640 de la commune de Montreux est considéré comme une seule parcelle pour tous les points concernant la réglementation communale [...]". La nouvelle parcelle n° 1'078 comprend désormais une surface de 2'790 m2. Ces biens-fonds sont colloqués en "zone de faible densité", "protection des sites", régie par les art. 33 ss du règlement sur le plan d'affectation et la police des constructions du 15 décembre 1972 de la commune de Montreux (ci-après: le RPGA 1972). Le nouveau plan général d'affectation, mis à l'enquête publique du 20 avril au 21 mai 2007 et adopté et réformé par le Conseil communal de Montreux le 2 septembre 2009, range ces terrains en "zone de coteau B" régie par les art. 9.1 ss du futur règlement communal sur le plan général d'affectation et la police des constructions (ci-après: le RPGA 2007). B. Le 28 octobre 2004, K._ SA avait déposé une demande de permis de construire sur la parcelle d'origine n° 1'078 portant, d'une part, sur un nouveau bâtiment d'habitation (ci-après: le bâtiment B), d'une surface au sol de 353 m2, avec parking souterrain, et, d'autre part, sur la transformation du bâtiment existant ECA n° 4'014. La Municipalité de Montreux (ci-après: la municipalité) avait délivré le 13 juillet 2005 le permis de construire, qui avait fait l'objet d'un recours devant le Tribunal administratif cantonal (devenu le 1er janvier 2008 la Cour de droit administratif et public du Tribunal cantonal; ci-après: le Tribunal cantonal) interjeté par B.A._ et A.A._, F.E._ et E.E._ ainsi que J.I._ et I.I._, propriétaires voisins. Par arrêt du 15 décembre 2005 (cause AC.2005.0169), le Tribunal cantonal a admis le recours et renvoyé le dossier à l'autorité intimée pour qu'elle procède à une enquête complémentaire au vu de la modification de l'implantation du bâtiment B; pour le surplus, il a confirmé le projet de construction. Après mise à l'enquête complémentaire du projet modifié, un nouveau permis de construire a été délivré le 22 mars 2006 que les propriétaires voisins ont porté devant le Tribunal cantonal, qui a rejeté le recours par arrêt du 6 septembre 2007 (cause AC.2006.0067). K._ SA a ensuite commencé les travaux de construction du bâtiment B et du parking souterrain, qui sont sur le point de s'achever. En revanche, elle a renoncé au projet de transformation de la villa de maître n° ECA 4'014, tout en procédant à sa démolition partielle. En lieu et place, elle a présenté un nouveau projet de construction. C. Le 7 juillet 2011, K._ SA a sollicité la délivrance d'un permis de construire portant sur la démolition du bâtiment ECA n° 4'014 et la construction d'un immeuble de deux logements (ci-après: le bâtiment A), d'une surface au sol de 260 m2. La demande de permis de construire vise aussi une dépendance et la création de trois places de parc extérieures sur la parcelle n° 12'640. Mis à l'enquête publique du 5 août au 5 septembre 2011, ce projet a suscité l'opposition de plusieurs propriétaires voisins, dont A.A._ et B.A._, C.C._ et D.C._, J.I._ et I.I._, ainsi que de G.G._ et H.G._, de même que de E.E._ et F.E._. Le 5 septembre 2011, la Centrale des autorisations (CAMAC) a communiqué à la municipalité sa synthèse comportant les autorisations spéciales des différents services cantonaux consultés. Par décision du 6 décembre 2011, la municipalité a levé les oppositions et délivré le permis de construire. Les opposants ont porté leur cause devant le Tribunal cantonal, qui, après avoir procédé à une vision locale, a rejeté les recours par arrêt du 9 novembre 2012 et confirmé la décision de la municipalité du 6 décembre 2011. D. Agissant par la voie du recours en matière de droit public, A.A._ et B.A._, C.C._ et D.C._, J.I._ et I.I._, E.E._ et F.E._ ainsi que G.G._ et H.G._ demandent au Tribunal fédéral de réformer l'arrêt du Tribunal cantonal du 9 novembre 2012 en ce sens que le permis de construire sollicité par K._ SA est refusé. Subsidiairement, ils concluent à l'annulation de l'arrêt attaqué et au renvoi de la cause au Tribunal cantonal pour nouvelle décision dans le sens des considérants. Ils se plaignent pour l'essentiel d'une constatation inexacte des faits et d'une application arbitraire du droit en lien avec l'autorité de chose jugée et la législation cantonale en matière d'aménagement du territoire et des constructions. La municipalité de Montreux et l'intimée concluent au rejet du recours. Les recourants ont répliqué et confirmé leurs conclusions. Par ordonnance du 23 janvier 2013, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif contenue dans le recours en tant qu'elle portait sur les nouvelles constructions autorisées par la municipalité de Montreux le 6 décembre 2011; elle était rejetée pour le surplus. 