Faits: A. A._ (ci-après: le recourant 1) exerce l'activité d'avocat et notaire dans le canton de Neuchâtel. Il fait partie de la même étude que l'avocat B._ (ci-après: le recourant 2). A._ a été le mandataire, en sa qualité de notaire et d'avocat, de feu C.X._ de 1980 à 1996, notamment pour le divorce, en 1995, de celui-ci d'avec sa première épouse avec laquelle il a eu trois enfants. Il a également instrumenté le contrat de mariage et le pacte successoral, pour lequel B._ est intervenu comme témoin, conclus en 1996 entre C.X._ et sa seconde épouse, D.X._ née Y._. Par la suite, les époux X._ ont confié la préparation de trois nouveaux pactes successoraux, qui reprennent les principes généraux de celui de 1996 tout en modifiant les quotités attribuées à chacun des héritiers, à un autre notaire. B. A la suite du décès de C.X._ survenu en 2004, A._, mandaté par les trois enfants issus du premier mariage de celui-là, s'est opposé au projet de convention de partage du 21 mars 2006 établi par les exécuteurs testamentaires. Ce litige fait l'objet d'une demande en réduction déposée par les trois enfants du défunt contre D.X._ devant le Tribunal cantonal du canton de Neuchâtel [ci-après: le Tribunal cantonal]. Les trois enfants, dans cette procédure, sont représentés par B._. Un deuxième procès oppose, devant un tribunal arbitral, la société E._ SA (société dont X._ était le principal actionnaire et le président du conseil d'administration et qui a été reprise par un de ses enfants avec un associé) à D.X._ au sujet d'une rente que la société versait à l'intéressée en vertu d'une convention d'actionnaires. Dans cette deuxième procédure, B._ représente la société susmentionnée. C. Par courrier du 4 décembre 2006, F._, avocat et mandataire de D.X._, a dénoncé A._ à l'Autorité de surveillance des avocates et avocats du canton de Neuchâtel pour conflit d'intérêts (ci-après: l'Autorité de surveillance). Cette Autorité a étendu d'office la procédure disciplinaire à B._, dès lors qu'il était l'associé de A._. Dans une décision du 3 avril 2007, ladite Autorité a retenu que A._ et B._ avaient violé la règle imposant aux avocats d'éviter tout conflit d'intérêts. Elle a condamné A._ à une amende de 2'000.- fr. et a infligé un blâme à B._. Par arrêt du 1er décembre 2008, l'Autorité de recours des avocates, des avocats et du notariat du canton de Neuchâtel (ci-après: l'Autorité de recours) a rejeté le recours des intéressés. Elle a retenu que les relations entre A._ et D.X._ relevaient du mandat. Or, la succession de feu C.X._ constituait à la fois l'objet du pacte successoral passé en 1996, parallèlement au contrat de mariage, et l'objet du litige opposant aujourd'hui les enfants du défunt et D.X._. Le rôle joué par A._ et B._, mandaté par les enfants du défunt, dans le litige relatif à la succession de feu C.X._, alors que A._ avait rédigé le pacte successoral entre feu C.X._ et sa veuve, relevait du conflit d'intérêts prohibé. Le fait que, d'une part, plusieurs années s'étaient écoulées depuis la conclusion du pacte successoral et du contrat de mariage et que, d'autre part, d'autres pactes successoraux avaient été conclus postérieurement à celui de 1996 par un autre notaire ne rendait pas caduques l'obligation de fidélité et celle liée au secret professionnel. D. Agissant par la voie du recours en matière de droit public, A._ et B._ demandent au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du 1er décembre 2008 de l'Autorité de recours "avec ou sans renvoi" (procédure 2C_26/2009). Ils invoquent une violation de l'art. 12 lettre c de la loi fédérale du 23 juin 2000 sur la libre circulation des avocats (ci-après: la loi sur les avocats ou LLCA; RS 935.61). L'Autorité de surveillance et L'Office fédéral de la justice n'ont pas formulé d'observations. L'Autorité de recours se réfère à son arrêt. E. Dans un deuxième temps, F._ a également dénoncé A._ à la Commission de surveillance du notariat du canton de Neuchâtel (ci-après: la Commission de surveillance). Dans une décision du 13 mars 2007, celle-ci a jugé que A._ avait gravement trompé la confiance de D.X._ et violé son devoir de fidélité, ainsi que le secret professionnel, en intervenant dans le litige successoral en cause comme mandataire des enfants de feu C.X._ et de la société E._ SA. Elle a infligé un blâme et une amende de 10'000.- fr. à A._, en retenant qu'il avait déjà été sanctionné peu de temps auparavant d'un blâme. Par arrêt du 1er décembre 2008, l'Autorité de recours a partiellement admis le recours de A._ à l'encontre de la décision du 13 mars 2007 de la Commission de surveillance. Elle a estimé qu'en l'espèce il ne se justifiait pas de prononcer un blâme en sus de l'amende de 10'000 fr. et a donc supprimé le blâme. Pour le surplus, ladite Autorité a rejeté le recours. Elle a retenu que les mandats des trois enfants de feu C.X._ acceptés par A._ étaient incompatibles avec les obligations résultant de l'activité de notaire mise précédemment au service de D.X._. F. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du 1er décembre 2008 de l'Autorité de recours et de renvoyer la cause à l'autorité cantonale pour nouvelle décision dans le sens des considérants (procédure 2C_41/2009). Il invoque une application arbitraire des dispositions cantonales topiques sur le notariat, ainsi qu'une violation de "l'obligation d'impartialité prévue par le droit fédéral" et du principe de la proportionnalité. L'Autorité de surveillance n'a pas formulé d'observations. L'Autorité de recours se réfère à son arrêt. 