Faits : A. En été 2018, le Ministère public a ouvert une procédure d'entraide CP/223/2018, à la demande des autorités allemandes, celles-ci instruisant une affaire contre divers protagonistes prévenus de faux dans les titres, dont C._, D._ et E._. En substance, les deux derniers nommés, dirigeants de sociétés appartenant au groupe F._, étaient soupçonnés d'avoir, entre 2009 et 2013, établi de faux contrats pour permettre à ces entités de présenter, sur le plan comptable, une situation financière meilleure qu'elle ne l'était en réalité. À cet effet, le concours de plusieurs sociétés avait été nécessaire, dont C._ était soit l'administrateur (G._ Ltd et ses filiales), soit le président (H._ SA, société valaisanne, dont E._ a été administrateur jusqu'en 2018, fonction qu'exerce désormais A._); C._ avait, pour échanger des informations dans ce cadre, utilisé son adresse e-mail auprès de I._ SA. A._, C._ et J._, tous trois résidents genevois, sont actionnaires de la société I._ SA, essentiellement active dans la gestion de trusts; le premier et le troisième nommés en sont les administrateurs. B._ est l'avocat de cette société depuis une date indéterminée, mais à tout le moins antérieure au mois de juin 2018. En exécution de la demande d'entraide, le Procureur a procédé à diverses perquisitions à Genève auprès de I._ SA et au domicile de C._ notamment, ainsi qu'à Zurich auprès de la société K._ - société qui est l'un des actionnaires du groupe F._ et dont C._ a été le directeur jusqu'en 2007. Ont, entre autres, été saisies, dans les locaux de I._ SA, les données électroniques (boîte e-mails) qui se trouvaient sur le poste de travail de C._ et, dans le logement de ce dernier, les données figurant sur l'ensemble de ses supports informatiques. En novembre 2018, B._ s'est constitué à la défense des intérêts, notamment, de I._ SA et C._. En accord avec le Ministère public, cet avocat a eu accès à l'entier des documents et données saisis - à tout le moins ceux se rapportant à ses mandants - afin de faciliter le tri de ceux-ci par des mots-clés qui avaient été choisis par les autorités allemandes pour limiter l'assiette des documents/données à leur transmettre. B. Parallèlement, le 11 septembre 2018, L._, bénéficiaire d'un trust dénommé M._, et les trustees de ce dernier ont déposé plainte pénale contre A._, C._, J._ et D._, des chefs de gestion déloyale et abus de confiance commis au préjudice du patrimoine de M._ (procédure P/17386/2018). En substance, ils reprochaient notamment aux trois premiers nommés d'avoir, de concert, le 3 avril 2018, en violation des devoirs de loyauté et de fidélité incombant au précédent trustee de M._, à savoir N._ Ltd dont ils étaient les animateurs depuis leur société genevoise I._ SA, indûment cédé à K._ la moitié des actions de O._ SA, entité appartenant à M._. Cette opération, dont le bénéficiaire était in fine D._, avait occasionné un dommage de GBP 30 millions environ. Le Procureur - qui n'est pas celui chargé de la procédure d'entraide - a prévenu C._, A._ et J._ de gestion déloyale (art. 158 CP) et abus de confiance (art. 138 CP) (procédure P/17386/2018). La défense des intérêts des trois premiers mis en cause est assurée, pour A._ par B._ (depuis le 19 décembre 2018), s'agissant de C._ par Mes P._ et Q._ et pour J._ par un autre mandataire. Le 19 décembre 2018, le Ministère public a perquisitionné les locaux de I._ SA et a notamment saisi les données informatiques issues des postes de travail de A._ et J._. Le 5 mars 2019, le Ministère public a ordonné l'apport d'éléments de preuve recueillis dans la procédure d'entraide, en particulier des pièces afférentes à K._ et de l'intégralité des données issues des supports informatiques professionnels et privés de C._. Celui-ci a requis, sous la plume de ses deux conseils, la mise sous scellés desdites données. Le Ministère public ayant refusé d'accéder à sa demande, C._ a formé un recours auprès de la Chambre pénale de recours de la Cour de justice de la République et canton de Genève (ci-après: la Cour de justice); celle-ci a admis le recours le 12 juin 2019 (ACPR/434/2019). C. Par décision du 27 mars 2019, le Procureur a considéré que Me B._ se trouvait dans une position de conflit d'intérêts concret, prohibé par l'art. 12 let. c de la loi fédérale sur la libre circulation des avocats du 23 juin 2000 (LLCA; RS 935.61) et a interdit à celui-ci de postuler à la défense des intérêts de A._ dans la procédure P/17386/2018. D. Par arrêt du 7 novembre 2019, la Cour de justice a, sur recours de A._ et B._, confirmé ce prononcé. En substance, elle a considéré que Me B._ pourrait avoir pris connaissance, dans le cadre de la procédure d'entraide, de davantage d'éléments que ceux qui figureront en définitive dans la procédure nationale. Selon la cour cantonale, si cet avocat se prévaut des courriels sous scellés/finalement écartés, il prend le risque de violer son secret professionnel vis-à-vis de C._ - qui avait clairement manifesté son intention, dans la procédure nationale, que certaines de ses données restent confidentielles -, tandis que s'il n'en fait pas état, alors qu'ils pourraient servir à la défense de A._, il est susceptible de violer son devoir de diligence à l'égard de ce dernier. Pour la cour cantonale, ce risque était accru par le fait que Me B._ avait été - potentiellement à l'époque des faits litigieux - et semblait être encore aujourd'hui, l'avocat de I._ SA. Pour l'instance précédente, le risque de conflit d'intérêt s'était d'ores et déjà concrétisé, au vu de l'attitude contradictoire adoptée par C._. E. Agissant par la voie du recours en matière pénale, A._ et B._ demandent au Tribunal fédéral d'annuler l'arrêt cantonal et de constater que Me B._ peut postuler à la défense des intérêts de A._ dans le cadre de la procédure P/17386/2018. Subsidiairement, ils concluent au renvoi de la cause à l'instance précédente pour nouvelle décision dans le sens des considérants. Par ordonnance du 30 décembre 2019, le Président de la Ire Cour de droit public du Tribunal fédéral a admis la requête d'effet suspensif et de mesures provisionnelles tendant à interdire au Ministère public tout acte d'instruction relevant du contradictoire ou faisant intervenir le droit d'être entendu des parties dans la procédure P/17386/2018. La cour cantonale et le Ministère public se réfèrent à l'arrêt attaqué, sans observations.