Faits :
A.
A.a. L'Etablissement hospitalier multisite cantonal (ci-après: l'EHM) était un établissement de droit public cantonal neuchâtelois, indépendant de l'Etat et doté de la personnalité juridique. Créé par la loi sur l'Etablissement hospitalier multisite cantonal du 30 novembre 2004, il avait repris l'ensemble des contrats de travail établis par les sept institutions hospitalières réunies en son sein au terme du processus d'intégration prévu par la loi. Les rapports de travail étaient régis par une convention collective de travail de droit public pour le secteur de la santé du canton de Neuchâtel (CCT Santé 21).
Les conditions de transposition des salaires des employés en service au 31 décembre 2006 ont fait l'objet de règles édictées par les organes de la convention et devenues applicables dès le 1 er janvier 2007. En substance, il était prévu que l'intégration de chaque employé dans sa nouvelle fonction, sa nouvelle classe de traitement et les échelons de celle-ci se ferait, dès le 1 er janvier 2007, selon le principe de la transposition au franc pour franc.
A.b. Le système de rémunération de la CCT Santé 21 est entré en vigueur le 1 er janvier 2007. Annexé à la CCT Santé 21, le règlement sur la rémunération (RRE) contient les principes de fixation du salaire du personnel hospitalier. Chaque fonction est colloquée dans une chaîne et dans une classe de la grille des fonctions (art. 5 al. 1 RRE). Selon l'art. 5.1 RRE, le salaire à l'engagement est fixé en fonction de l'expérience acquise et attestée (al. 1); les années d'expérience professionnelle dans une fonction équivalente donnent droit chacune à un échelon (al. 2), les années d'expérience professionnelle utiles à la fonction à trois quarts d'échelon (al. 3) et les années d'autres expériences professionnelles ou d'expérience de vie à un quart d'échelon (al. 5).
Le 1 er novembre 2007, des employés de l'EHM ont constitué une association appelée "Groupement du personnel de l'Etablissement hospitalier neuchâtelois" (ci-après: le Groupement), dans le but d'intenter "une action en vue de la reconnaissance de l'ancienneté professionnelle complète pour le calcul des échelons de collocation de la CCT 21".
A.c. Le 27 mai 2009, 170 membres du Groupement ont ouvert action devant le Tribunal administratif (devenu le 1er janvier 2011 la Cour de droit public du Tribunal cantonal) du canton de Neuchâtel. Alléguant que l'art. 5.1 RRE n'avait pas été respecté à leur égard par la transposition salariale effectuée au 1er janvier 2007, ils ont conclu principalement à la constatation de l'inégalité de traitement entre anciens et nouveaux employés en ce qui concernait la collocation des années d'expérience dans la fixation de leur salaire, et subsidiairement au renvoi de la cause à l'EHM pour nouvel examen des dossiers et transposition des salaires à l'échelon correspondant à leurs années d'expérience, avec effet rétroactif au 1 er janvier 2007. Parallèlement à cette action de droit administratif, d'autres employés de l'EHM ont également saisi la juridiction cantonale.
Par arrêt du 29 octobre 2012, la Cour de droit public a constaté que le système de transposition salariale appliqué était constitutif d'une inégalité de traitement entre les anciens employés repris par l'EHM et les nouveaux employés engagés par lui dès le 1 er janvier 2007; elle a ainsi transmis le dossier à l'EHM pour réexamen individuel de la situation de chacun des demandeurs. Le recours en matière de droit public et le recours constitutionnel subsidiaire interjetés par l'EHM contre cet arrêt ont été respectivement rejeté et déclaré irrecevable par le Tribunal fédéral (arrêt 8C_969/2012 du 2 avril 2013).
A.d. Au printemps 2014, les collaborateurs de l'EHM ont été informés qu'ensuite de l'arrêt du Tribunal fédéral du 2 avril 2013, la direction générale s'était attachée à réétudier la collocation de l'ensemble du personnel dont le salaire avait été transposé et que les salaires concernés seraient corrigés selon des modalités différenciées: les salaires des personnes ayant saisi la Cour de droit public seraient mis à niveau avec effet au 1 er janvier 2014 et une compensation partielle avec effet au 1 er mai 2009 - mois de la saisine de la Cour de droit public - leur serait versée; quant aux personnes n'ayant pas saisi la Cour de droit public, leur salaire serait aussi corrigé, au plus tard en 2015, mais sans effet rétroactif.
L'EHM a ainsi mis en place, pour les personnes ayant saisi la Cour de droit public, un rattrapage partiel de la différence de salaire à laquelle les employés en service au 31 décembre 2006 avaient été soumis entre le 27 mai 2009 et le 31 décembre 2013. Ce rattrapage échelonné et progressif a consisté à compenser 20 % de la perte de salaire pour 2009 (mai à décembre), 40 % pour 2010, 60 % pour 2011, 80 % pour 2012 et 100 % pour 2013.
B.
B.a. Le 30 septembre 2016, 109 membres du Groupement (ci-après: les demandeurs) ont ouvert action devant la Cour de droit public du Tribunal cantonal, en concluant à ce qu'il soit ordonné à l'EHM - devenu le 1er janvier 2017 l'Hôpital neuchâtelois, puis le 1er novembre 2019 le Réseau hospitalier neuchâtelois (ci-après: le RHNe ou le défendeur) - de verser à chacun d'entre eux l'intégralité de l'arriéré de salaire correspondant à la transposition correcte de son salaire à l'échelon correspondant à ses années d'expérience, dès le 1 er janvier 2007 (conclusions dont ils ont ultérieurement chiffré le montant total à 2'055'840 fr. 55).
B.b. Le défendeur a conclu à l'irrecevabilité de la demande, subsidiairement à son rejet. Il a contesté que l'inégalité de traitement constatée par l'arrêt du 29 octobre 2012 dût être éliminée par une compensation totale dès le 1 er janvier 2007 de la différence de traitement entre les employés présents au 31 décembre 2006 et ceux engagés ultérieurement. Il a fait valoir que la question d'un effet rétroactif avait été tranchée par l'arrêt du 29 octobre 2012, que la correction était intervenue dans un délai raisonnable puisque dès 2013, les membres du Groupement avaient vu leur salaire corrigé à 100 %, et que la correction par paliers était admissible. Il a déposé un tableau récapitulatif des adaptations salariales concernant les membres du Groupement.
B.c. A l'invitation du juge instructeur de la Cour de droit public, l'avocate des demandeurs a produit des procurations actualisées rédigées en vue de l'action du 30 septembre 2016, sauf pour sept d'entre eux. Toujours à la demande du juge instructeur, l'avocate des demandeurs a déposé des tableaux indiquant notamment pour chacun des demandeurs - sauf deux d'entre eux, qui ne faisaient plus partie du Groupement - la classe et l'échelon effectif auxquels il avait été colloqué, la classe et l'échelon auxquels il estimait qu'il aurait dû être colloqué ainsi que la différence (en %) entre le montant de l'échelon demandé et le montant de l'échelon effectif, et ce pour chacune des années pour lesquelles était invoquée une inégalité de traitement.
B.d. Par arrêt du 17 juin 2020, la Cour de droit public a rejeté la demande, dans la mesure où celle-ci n'était pas irrecevable (ce qui était le cas pour sept des demandeurs) ou ne devait pas être classée faute d'objet (ce qui était le cas pour deux des demandeurs); elle a mis les frais de la cause, par 66'000 fr., à la charge solidaire des demandeurs, qu'elle a condamnés solidairement à verser au défendeur une indemnité de 40'000 fr. à titre de dépens.
C.
Les 100 demandeurs dont la demande n'a pas été déclarée irrecevable ou classée faute d'objet interjettent un recours en matière de droit public ainsi qu'un recours constitutionnel subsidiaire contre cet arrêt, en concluant principalement à sa réforme en ce sens que le RHNe doive leur payer un montant total de 2'055'840 fr. 55, à répartir selon le tableau récapitulatif figurant au dossier, correspondant à la transposition correcte de leurs salaires à l'échelon correspondant à leurs années d'expérience, dès le 1er janvier 2007, avec intérêts à 5 % l'an dès le prononcé de l'arrêt à rendre. A titre subsidiaire, en cas de rejet de leurs conclusions au fond, ils concluent à la réforme de l'arrêt attaqué en ce sens qu'il ne soit pas perçu de frais judiciaires - ou à tout le moins pas d'un montant supérieur à 2750 fr. - ni alloué de dépens pour la procédure devant l'autorité précédente. Plus subsidiairement, ils concluent à l'annulation de l'arrêt entrepris et au renvoi de la cause à l'autorité précédente pour nouvel arrêt dans le sens des considérants.
L'intimé conclut au rejet des recours. L'autorité précédente ne s'est pas déterminée. Les recourants ont répliqué.
Considérant en droit :
1.
L'arrêt entrepris concerne des rapports de travail de droit public au sens des art. 83 let. g et 85 al. 1 let. b LTF. Il tranche une contestation pécuniaire (cf. art. 83 let. g LTF) et la valeur litigieuse dépasse largement le seuil de 15'000 fr. (art. 51 al. 1 let. a et 85 al. 1 let. b LTF) ouvrant la voie du recours en matière de droit public en ce domaine. Les recourants ont la qualité pour recourir, dès lors qu'ils ont succombé dans leurs conclusions en paiement prises devant l'autorité précédente et qu'ils ont ainsi un intérêt digne de protection à l'annulation ou à la modification de l'arrêt entrepris (art. 89 al. 1 LTF). Interjeté en temps utile (art. 100 al. 1 LTF) et dans les formes requises (art. 42 LTF), contre une décision finale (art. 90 LTF) prise par l'autorité cantonale de dernière instance (art. 86 al. 1 let. d LTF), le recours en matière de droit public est partant recevable. En conséquence, le recours constitutionnel subsidiaire formé simultanément par les recourants est irrecevable (art. 113 LTF a contrario).
2.
Le Tribunal fédéral applique le droit d'office (art. 106 al. 1 LTF). Toutefois, il n'examine la violation de droits fondamentaux ainsi que celle de dispositions de droit cantonal et intercantonal que si ce grief a été invoqué et motivé par le recourant (art. 106 al. 2 LTF). Sauf exceptions non pertinentes en l'espèce (cf. art. 95 let. c, d et e LTF), on ne peut pas invoquer la violation du droit cantonal ou communal en tant que tel devant le Tribunal fédéral (art. 95 LTF a contrario). Il est néanmoins possible de faire valoir que son application viole le droit fédéral, en particulier l'interdiction de l'arbitraire (art. 9 Cst.) ou d'autres droits constitutionnels. Le Tribunal fédéral n'examine alors de tels moyens que s'ils sont formulés conformément aux exigences de motivation qualifiée prévues à l'art. 106 al. 2 LTF (ATF 142 V 577 consid. 3.2 et la référence). Appelé à revoir l'interprétation d'une norme cantonale ou communale sous l'angle de l'arbitraire, le Tribunal fédéral ne s'écarte de la solution retenue par l'autorité cantonale de dernière instance que si celle-ci apparaît insoutenable, en contradiction manifeste avec la situation effective, adoptée sans motifs objectifs et en violation d'un droit certain. En revanche, si l'application de la loi défendue par l'autorité cantonale ne s'avère pas déraisonnable ou manifestement contraire au sens et au but de la disposition ou de la législation en cause, cette interprétation sera confirmée, même si une autre solution - même préférable - paraît possible (ATF 144 I 113 consid. 7.1 et la référence).
3.
3.1. Les premiers juges ont d'abord examiné pour quelle période les recourants pouvaient prétendre le cas échéant à un rattrapage de salaire pour inégalité de traitement.
3.1.1. La cour cantonale a exposé que les recourants faisaient valoir que le système de rattrapage mis en place par l'intimé n'éliminait pas les inégalités constatées par arrêt du 29 octobre 2012 et demandaient, en se référant à l'ATF 117 la 262, que cette inconstitutionnalité fût corrigée par une rétribution de l'intégralité de l'arriéré de salaire liée à la transposition de leurs salaires à l'échelon correspondant à leurs années d'expérience dès le 1er janvier 2007, date à laquelle le début de l'inégalité de traitement avait eu lieu.
Toutefois, l'ATF 117 Ia 262 ne permettait pas de donner suite à leur demande, dès lors qu'il avait trait au droit à l'égalité salariale entre hommes et femmes, et non à une inégalité salariale reposant sur d'autres motifs que le sexe, et que les recourants ne prétendaient pas que le nouveau système de rémunération en vigueur dès le 1er janvier 2007 était constitutif d'une discrimination fondée sur le sexe.
3.1.2. L'autorité cantonale a ensuite considéré que les recourants ne pouvaient pas obtenir un versement rétroactif avec effet au 1 er janvier 2007 en se fondant sur le principe général de l'égalité. En effet, comme la Cour de droit public l'avait déjà relevé dans son arrêt du 29 octobre 2012, l'action déposée le 27 mai 2009 ne pouvait pas déployer un effet rétroactif, car cela était clairement contraire à la jurisprudence cantonale applicable en la matière (arrêts CDP.2009.254 du 29 octobre 2012 consid. 5 et les références citées; CDP.2009.125 du 17 octobre 2013 consid. 2c).
Par ailleurs, selon la jurisprudence fédérale, le principe général d'égalité posé à l'art. 8 al. 1 Cst. conférait seulement un droit à ce qu'une inégalité salariale fût corrigée d'une manière appropriée et dans un délai convenable, mais ne fondait aucune prétention au versement rétroactif d'une rémunération exempte d'inégalité (ATF 131 I 105 consid. 3.7; arrêts 8C_558/2014 du 13 mars 2015 consid. 5.4.2, 8C_639/2013 du 30 juillet 2014 consid. 6.1). Par conséquent, les conclusions des recourants tendant à obtenir le paiement d'une différence de salaire pour la période antérieure à leur précédente action déposée le 27 mai 2009 devaient être rejetées.
3.1.3. Comme les recourants ne faisaient pas valoir d'inégalité de traitement au-delà du 31 décembre 2013, la période pour laquelle il y avait lieu d'examiner le grief d'inégalité de traitement était ainsi celle comprise entre mai 2009 et fin 2013.
3.2. Les recourants contestent le refus de la cour cantonale d'accorder un effet rétroactif à leur action déposée le 27 mai 2009. Ils soutiennent que dès l'entrée en vigueur de la CCT Santé 21 le 1er janvier 2007, ils seraient intervenus auprès de toutes les instances mentionnées dans cette convention collective, qui se seraient déclarées incompétentes, avant de consulter leur avocate qui n'aurait pas eu d'autre choix que d'ouvrir une action de droit administratif. En refusant d'accorder à cette action un effet rétroactif à la date de l'entrée en vigueur de la CCT, source de l'inégalité de traitement, la cour cantonale aurait violé la prohibition de l'arbitraire ainsi que le principe de l'égalité consacré par l'art. 8 al. 1 Cst.
3.3. A titre liminaire, il y a lieu d'observer que, contrairement à ce que soutient l'intimé, le fait que la cour cantonale avait déjà relevé dans les motifs de son premier arrêt du 29 octobre 2012 que l'action déposée le 27 mai 2009 ne pouvait pas déployer un effet rétroactif n'empêche pas les recourants de contester l'arrêt du 17 juin 2020 en tant qu'il rejette leurs conclusions pour la période antérieure à mai 2009. En effet, l'autorité de la chose jugée - qui interdit de remettre en cause, dans une nouvelle procédure entre les mêmes parties, une prétention identique à celle qui a été définitivement jugée (ATF 142 III 210 consid. 2.1 et les arrêts cités) - est limitée au seul dispositif du jugement (arrêt 9C_58/2012 du 8 juin 2012 consid. 4.2, non publié à l'ATF 138 V 298). Or l'arrêt du 29 octobre 2012 se bornait dans son dispositif à constater que le système de transposition salariale appliqué était constitutif d'une inégalité de traitement entre les anciens employés repris par l'intimé et les nouveaux employés engagés par lui dès le 1er janvier 2007, et à transmettre le dossier à l'intimé pour réexamen individuel de la situation de chacun des recourants. Ce n'est que dans son arrêt du 17 juin 2020 que la juridiction cantonale a rejeté les conclusions des recourants pour la période antérieure à mai 2009, ce qu'elle n'aurait pas pu faire si elle avait déjà statué sur ce point avec l'autorité de la chose jugée.
3.4. Cela étant, les recourants ne démontrent nullement en quoi le raisonnement de l'autorité cantonale - qui repose d'une part sur le fait que la jurisprudence cantonale applicable en la matière ne permet pas de reconnaître un effet rétroactif à l'action déposée le 27 mai 2009, et d'autre part sur le fait qu'il n'est pas contraire à l'art. 8 al. 1 Cst. de corriger une inégalité salariale au titre de la garantie générale de l'égalité de traitement avec effet seulement depuis le moment où l'intéressé fait valoir sa prétention - violerait la prohibition de l'arbitraire ou d'autres droits constitutionnels.
Contrairement à la garantie à une rémunération égale de l'homme et de la femme qui confère un droit subjectif en vertu de la réglementation spécifique (art. 4 al. 2, 3e phrase, aCst.; art. 8 al. 3 Cst.; loi fédérale du 24 mars 1995 sur l'égalité entre femmes et hommes [LEg; RS 151.1]), la garantie générale de l'égalité de traitement de l'art. 8 al. 1 Cst. ne confère pas directement un droit subjectif à un salaire égal en cas de rémunération discriminatoire non fondée sur le sexe, mais seulement un droit à la suppression de l'inégalité. De la garantie générale de l'égalité de traitement découle l'obligation de l'employeur public de rémunérer un même travail avec un même salaire. Dans les limites de l'interdiction de l'arbitraire, les autorités disposent d'une grande marge d'appréciation dans le choix des critères déterminants pour la fixation de la rémunération. Cette marge d'appréciation a son importance lorsqu'il s'agit de supprimer une inégalité salariale non fondée sur le sexe. Contrairement à la garantie d'une rémunération égale de l'homme et de la femme, la garantie générale de l'égalité de traitement ne confère pas en droit fédéral une prétention directe au paiement d'un salaire égal à titre rétroactif. La Constitution exige seulement que l'inégalité soit éliminée d'une manière appropriée et dans un délai raisonnable. A cet égard, il est justifié de prendre en considération le moment auquel l'intéressé a contesté l'inégalité en question pour la première fois. Selon la jurisprudence, il n'est pas insoutenable ni arbitraire de corriger une inégalité salariale au titre de la garantie générale de l'égalité de traitement avec effet seulement depuis le moment où l'intéressé fait valoir sa prétention (sur le tout: ATF 131 I 105 consid. 3.6 et 3.7; arrêt 8C_104/2010 du 20 septembre 2010 consid. 5.2).
En l'espèce, il est constant que les prétentions des recourants sont fondées sur la garantie générale de l'égalité de traitement (art. 8 al. 1 Cst.) et non sur la garantie à une rémunération égale de l'homme et de la femme (art. 8 al. 3 Cst.). La cour cantonale pouvait donc, sans violer le droit fédéral, rejeter ces prétentions en tant qu'elles portaient sur la période antérieure à l'ouverture d'action. Au surplus, les recourants ne prétendent pas qu'ils n'auraient pas pu, en faisant preuve de la diligence requise, déposer leur action en 2007 déjà.
4.
4.1. Les premiers juges ont ensuite examiné la manière dont l'intimé avait mis en oeuvre l'injonction qui lui avait été faite de corriger l'inégalité de traitement constatée par arrêt du 29 octobre 2012.
4.1.1. La cour cantonale a rappelé que l'art. 5.1 RRE avait été rédigé dans un contexte de préoccupation relative à une pénurie de personnel soignant. Toutefois, dès lors que les critères de cette disposition étaient applicables seulement à l'entrée en service, qu'ils n'avaient pas été pris en compte pour la transposition du salaire du personnel en place et qu'il n'était pas prévu que cette différence de traitement fût limitée dans le temps, il en était résulté l'inégalité de traitement constatée dans l'arrêt du 29 octobre 2012. Dans cet arrêt, la Cour de droit public, considérant qu'il ne lui appartenait pas de déterminer elle-même les correctifs propres à remédier à cette inégalité de traitement mais qu'il revenait à l'intimé de procéder à un réexamen individuel de la classification de chacun des recourants ou à un réexamen intégral du système de transposition, avait transmis le dossier à l'intimé à cette fin (cf. arrêt 8C_969/2012 précité consid. 4). La procédure ultérieure ouverte par demande du 30 septembre 2016 s'inscrivait dans la suite de cet arrêt et portait sur le point de savoir si les mesures prises par l'intimé avaient été propres à remédier à l'inégalité de traitement constatée en son temps, respectivement si la différence de traitement qui demeurait après les mesures prises par l'intimé était admissible au regard de la jurisprudence en la matière.
4.1.2. Les juges cantonaux ont exposé que selon la jurisprudence du Tribunal fédéral, des circonstances qui n'ont pas trait à la personne ou à l'activité de l'employé peuvent justifier, à tout le moins temporairement, des différences de salaire, comme une situation conjoncturelle rendant plus difficile le recrutement du personnel ou des contraintes budgétaires. Des conditions de travail plus favorables réservées au personnel nouvellement engagé sont admissibles pour autant que la différence de traitement qui en découle par rapport au personnel engagé précédemment reste dans des limites acceptables.
4.1.3. La cour cantonale a relevé que dans d'autres affaires relatives à des inégalités de traitement entre le personnel repris par l'intimé au 1er janvier 2007 et le personnel nouvellement engagé à partir de cette date, elle avait jugé que des différences de salaire comprises entre respectivement 4,86 %-11,66 %, 5,98 %-9,47 %, 6,90 %-16,29 %, 6,60 %-10,82 %, 2,11 %-5,98 % et enfin 8,64 %-13,97 % pendant huit ans pouvaient être considérées comme acceptables tant en ce qui concernait leur ampleur que leur durée prises isolément, et à plus forte raison en les considérant de manière combinée.
Dans le cas des recourants, l'autorité précédente a observé que les calculs effectués à partir des indications fournies dans leurs tableaux aboutissaient à des différences de traitement dont la plus grande ampleur était inférieure à la plus grande différence (16,29 %) constatée dans les affaires précitées, sous réserve de deux cas. Il pouvait ainsi être considéré que ces différences de traitement - qui avaient porté sur une période de quatre ans - étaient encore admissibles, d'autant que les chiffres résultant des tableaux ne prenaient pas en compte les montants versés par l'intimé selon les modalités rappelées plus haut (cf. let. A.d supra).
Les juges cantonaux ont ensuite examiné le cas des deux recourants dont la différence de traitement maximale était selon eux supérieure à 16,29 %. S'agissant de la recourante A._ la différence de salaire variait entre 20,31 % (en 2009) et 0 % (en 2013). Si le premier chiffre paraissait important, il restait néanmoins admissible vu qu'il ne portait que sur une seule année, les différences tombant ensuite à des niveaux bien moindres (13,24 % en 2010, 8,20 % en 2011 et 3,62 % en 2012) pour ensuite disparaître dès 2014. S'agissant de la recourante B._, la différence de salaire variait entre 14,73 % (en 2009) et 3,38 % (en 2013) et était ainsi encore admissible.
4.1.4. Devant la cour cantonale, les recourants ont produit deux courriers anonymisés des 2 avril et 6 juin 2012, dans lesquels l'intimé adaptait les salaires de deux employés à la hausse avec effet rétroactif au 1er janvier 2007; ils ont soutenu sur cette base que l'intimé avait "ponctuellement et apparemment de manière aléatoire (...) procédé à des adaptations salariales à son bon vouloir, constitutives de nouvelles inégalités de traitement". Les juges cantonaux ont retenu à cet égard, sur la base des explications fournies par l'intimé, que les corrections de salaire en question étaient intervenues à la suite de contrôles concernant d'une part l'application du système de rémunération quant aux nouveaux engagements dès 2007 et d'autre part la bonne application des règles fixées par la transposition salariale communément admises à cette période-là, de sorte qu'il s'agissait de corriger des erreurs dans la fixation des salaires qui n'avaient aucun lien avec l'inégalité consécutive à l'ancienneté faisant l'objet de la présente procédure.
4.2.
4.2.1. Selon la jurisprudence du Tribunal fédéral, lorsque des inégalités de traitement sur le plan salarial ne reposent pas sur des motifs objectifs tenant à la personne ou à l'activité du travailleur (tels que l'âge, l'ancienneté, l'expérience, les charges familiales, les qualifications, le genre et la durée de la formation requise pour le poste, le temps de travail, les horaires, le cahier des charges, l'étendue des responsabilités ou les prestations; cf. ATF 131 I 105 consid. 3.1; 123 I 1 consid. 6a-c), des différences de salaire peuvent être justifiées, à tout le moins temporairement, par d'autres circonstances qui n'ont pas trait à la personne ou à l'activité du travailleur, telles qu'une situation conjoncturelle rendant plus difficile le recrutement du personnel ou des contraintes budgétaires de la collectivité publique (arrêts 8C_969/2012 précité 2013 consid. 2.2; 2P.70/2004 du 17 janvier 2005 consid. 2.1 et 3.1; 2P.10/2003 du 7 juillet 2003 consid. 3.3). Il appartient à l'employeur qui invoque de tels motifs d'en établir clairement l'existence (cf. ATF 113 Ia 107 consid. 4a in fine, s'agissant de l'égalité entre hommes et femmes).
4.2.2. Dans ce cadre, des conditions de travail plus favorables réservées au personnel nouvellement engagé sont admissibles pour autant que la différence de traitement qui en découle par rapport au personnel engagé précédemment reste dans des limites acceptables (arrêts 2P.10/2003 précité consid. 3.4; 8C_732/2015 du 14 septembre 2016 consid. 4.2; 8C_649/2010 du 1er mars 2011 consid. 7.5 et 7.6; 2P.41/2004 du 21 juin 2004 consid. 3.3; 2P.222/2003 du 6 février 2004 consid. 4.3). C'est ainsi qu'une réglementation prévoyant une classification plus favorable pour le personnel nouvellement engagé a été jugée acceptable dans la mesure où elle entraînait une différence de salaire de l'ordre de 100 fr. par mois (arrêt 2P.10/2003 précité). Dans une autre affaire (arrêt 2P.70/2004 précité), la suppression de mesures d'économie sous la forme de paliers d'attente pour les enseignants nouvellement engagés avait provoqué une inégalité de traitement par rapport aux enseignants engagés après cette suppression; cette inégalité a été jugée admissible du fait que la différence de salaire était relativement modique (entre 1 % et 7,5 % durant plusieurs années). Le caractère temporaire d'une inégalité de traitement relative au système salarial fait partie des circonstances concrètes au regard desquelles il convient d'examiner si une différence de traitement salarial dépasse ou non le cadre admissible (arrêts précités 8C_732/2015 consid. 4.2; 8C_969/2012 consid. 3.2.2; 2P.222/2003 consid. 4.7 et 4.8, où une différence comprise entre 8,3 % et 15,4 % sur une période de cinq ans a été jugée encore admissible).
4.3.
4.3.1. Se plaignant d'une violation de l'art. 8 al. 1 Cst., les recourants soutiennent d'abord que le rattrapage échelonné et progressif mis en place par l'intimé pour les employés qui avaient saisi la Cour de droit public - consistant à compenser 20 % de la perte de salaire pour 2009 (mai à décembre), 40 % pour 2010, 60 % pour 2011, 80 % pour 2012 et 100 % pour 2013 (cf. let. A.d supra) - ne saurait être admissible que pour autant que l'intimé ait pu justifier les raisons pour lesquelles les inégalités constatées n'auraient pas pu être compensées à 100 % dès le 1er janvier 2007, ou au moins dès le 1er mai 2009. Or tel n'aurait pas été le cas.
En l'espèce, l'autorité précédente a retenu en fait, sur la base des preuves fournies par l'intimé en procédure cantonale, que la prise en compte de l'expérience acquise pour fixer le salaire lors de l'engagement de nouveaux employés, telle que prévue à l'art. 5.1 RRE, trouvait son origine dans les difficultés que rencontraient les institutions de soins neuchâteloises à recruter du personnel, soit dans un contexte de préoccupation relative à une pénurie de personnel soignant. Cette constatation lie le Tribunal fédéral, en l'absence de grief de constatation arbitraire des faits (art. 97 al. 1 et art. 105 al. 2 LTF; ATF 142 II 355 consid. 6). L'intimé ayant ainsi démontré l'existence de difficultés de recrutement du personnel soignant (cf. consid. 4.2.1 supra), il reste à examiner si l'inégalité de traitement temporaire entre anciens et nouveaux employés de l'intimé, telle qu'elle résulte du système de rattrapage progressif et échelonné mis en place à la suite de l'arrêt de la Cour de droit public du 29 octobre 2012 et de l'arrêt du Tribunal fédéral du 2 avril 2013 (cf. let. A.d supra), reste dans des limites acceptables (cf. consid. 4.2.2 supra). Or à cet égard, les recourants ne tentent pas même de démontrer en quoi le raisonnement de la cour cantonale, au regard des différences de salaire constatées sur la période de quatre ans litigieuse, dont l'ampleur est allée décroissant en raison du système de rattrapage échelonné mis en place par l'intimé, consacrerait une violation de l'art. 8 al. 1 Cst. et de la jurisprudence y relative.
4.3.2. C'est par ailleurs en vain que les recourants soutiennent que le système en question aurait pour conséquence de créer de nouvelles inégalités de traitement du fait que les employés ayant quitté l'employeur avant 2014 bénéficieraient d'un pourcentage global de rattrapage inférieur à ceux ayant été engagés pendant toute cette période. En effet, les employés ayant quitté l'employeur avant le terme du programme de rattrapage progressif se trouvent objectivement dans une situation différente de ceux qui sont restés au service de l'employeur et tous sont traités exactement de la même manière pour chacune des années pendant lesquelles ils ont travaillé pour l'intimé.
4.3.3. Enfin, en tant que les recourants font grief à la cour cantonale d'avoir rejeté arbitrairement le reproche d'inégalité qu'ils avaient formulé en lien avec la production des deux courriers anonymisés des 2 avril et 6 juin 2012 (cf. consid. 4.1.4 supra), leur grief apparaît insuffisamment motivé au regard des exigences de motivation qualifiée prévues à l'art. 106 al. 2 LTF (cf. consid. 2 supra).
4.3.4. Il s'ensuit que l'arrêt attaqué échappe à la critique en tant qu'il rejette la demande en paiement des recourants pour la période allant de mai 2009 à fin 2013.
5.
A titre subsidiaire, soit en cas de rejet de leurs conclusions principales, les recourants contestent les frais et dépens mis à leur charge.
5.1.
5.1.1. La cour cantonale a exposé que selon la pratique en matière de litiges relatifs aux rapports de service, il n'était pas perçu de frais judiciaires lorsque la valeur litigieuse n'excédait pas 30'000 fr. Dès lors que les recourants avaient chiffré leurs conclusions à 2'055'840 fr. 55, les frais de la cause devaient être mis à leur charge en application de l'art. 60 al. 3 de la loi cantonale neuchâteloise du 27 juin 1979 sur la procédure et la juridiction administrative (LPJA; RS/NE 152.130). S'agissant du montant desdits frais, l'art. 12 al. 1 de la loi cantonale neuchâteloise du 6 novembre 2019 fixant le tarif des frais, des émoluments de chancellerie et des dépens en matière civile, pénale et administrative (LTFrais; RS/NE 164.1) - applicable par renvoi de l'art. 51 LTFrais - prévoyait que l'émolument forfaitaire de décision pour une valeur supérieure à 1'000'000 fr. se montait à 4 % de celle-ci, ce qui conduirait en l'espèce à un émolument de 82'230 fr. Relevant toutefois que l'autorité pouvait s'écarter du tarif lorsque sa mise à contribution ne justifiait pas l'émolument calculé (art. 12 al. 3 LTFrais), la cour cantonale a considéré que sa mise à contribution importante dans cette cause justifiait un émolument forfaitaire de décision de 60'000 fr., auquel s'ajoutaient les débours calculés forfaitairement à raison de 10 % de l'émolument (art. 52 LTFrais). C'étaient ainsi des frais totaux de 66'000 fr. qui devaient être mis à la charge des recourants, solidairement entre eux.
5.1.2. Les juges cantonaux ont ensuite exposé que l'intimé pouvait prétendre à des dépens, conformément à l'art. 60 al. 3 LPJA. Selon les art. 58 et 59 LTFrais - applicables par renvoi de l'art. 67 LTFrais -, les honoraires étaient proportionnés à la valeur litigieuse et étaient fixés dans les limites du tarif, en fonction du temps nécessaire à la cause, de sa nature, de son importance, de sa difficulté, du résultat obtenu ainsi que de la responsabilité encourue par le représentant. Lorsque la valeur litigieuse était supérieure à 2'000'000 fr., le tarif prévoyait que les honoraires, taxe sur la valeur ajoutée (TVA) non comprise, étaient fixés jusqu'à 3 % de cette valeur litigieuse. En l'espèce, des honoraires de 40'000 fr. se justifiaient et devaient être mis à la charge solidaire des recourants.
5.2.
5.2.1. A titre principal, les recourants font valoir que les dispositions légales sur la base desquelles ils ont été condamnés à payer des frais judiciaires et des dépens sont entrées en vigueur - avec des dispositions transitoires prévoyant que les dispositions modifiées s'appliquent aux procédures pendantes à l'entrée en vigueur de ces modifications - le 15 juin 2020, soit deux jours avant le prononcé de l'arrêt entrepris. Cela violerait le principe de la non-rétroactivité des lois, qui découle du principe de la légalité (art. 5 al. 1 Cst.), ainsi que l'art. 9 al. 2 Cst./NE (RS 131.233), aux termes duquel sont interdites les lois rétroactives qui entraînent des charges supplémentaires pour les particuliers. En outre, la juridiction cantonale aurait violé le principe de la bonne foi en rendant son arrêt deux jours après l'entrée en vigueur des nouvelles dispositions alors qu'elle avait gardé la cause à juger pendant plus d'un an.
A titre subsidiaire, pour le cas où l'on considérerait que l'autorité précédente était en droit d'appliquer les nouvelles dispositions entrées en vigueur le 15 juin 2020, les recourants critiquent la quotité des frais judiciaires et des dépens mis à leur charge.
5.2.2. Selon la jurisprudence, l'interdiction de la rétroactivité (proprement dite) des lois, qui résulte du droit à l'égalité (art. 8 al. 1 Cst.), du principe de la légalité (art. 5 al. 1 Cst.) ainsi que de l'interdiction de l'arbitraire et de la protection de la bonne foi (art. 9 Cst.), fait obstacle à l'application d'une norme à des faits entièrement révolus avant son entrée en vigueur, car les personnes concernées ne pouvaient pas, au moment où ces faits se sont déroulés, connaître les conséquences juridiques découlant de ceux-ci et se déterminer en connaissance de cause (ATF 144 I 81 consid. 4.2; 138 I 189 consid. 3.4; 137 II 371 consid. 4.2; 126 V 134 consid. 4a; 122 V 405 consid. 3b/aa). Il n'y a toutefois pas de rétroactivité proprement dite lorsque le législateur entend réglementer un état de choses qui, bien qu'ayant pris naissance dans le passé, se prolonge au moment de l'entrée en vigueur du nouveau droit; cette rétroactivité improprement dite est en principe admise, sous réserve du respect des droits acquis (ATF 140 V 154 consid. 6.3.2; 138 I 189 consid. 3.4 précité; 137 II 371 consid. 4.2 précité; 122 V 405 consid. 3b/aa précité).
D'autre part, le principe de la bonne foi, ancré à l'art. 9 Cst., ne saurait, en règle ordinaire, être invoqué en cas de changement de législation. Toutefois, dans certaines circonstances, doctrine et jurisprudence déduisent du droit à la protection de la bonne foi que l'adoption de règles transitoires doit permettre aux administrés de s'adapter à la nouvelle situation légale, même si une grande liberté doit, en ce domaine, être reconnue au législateur. En effet, lors de modifications de règles de droit, la protection de la confiance peut se justifier - au même titre qu'en présence d'un renseignement erroné - à l'égard des dispositions prises de bonne foi par les intéressés et sur lesquelles il leur est difficile de revenir. Il faut le cas échéant procéder à une pesée des intérêts en présence, à savoir d'une part la protection de la bonne foi et d'autre part le principe de la légalité, qui exige que, sauf motif particulier, les lois ou ordonnances entrent en vigueur sans retard (ATF 122 V 405 consid. 3b/bb et les références).
5.2.3. Dans un arrêt 2C_1043/2018 du 27 mai 2019, le Tribunal fédéral a constaté que la LPJA ne contenait pas de disposition prévoyant qu'une action de droit administratif pouvait donner lieu à la perception de frais judiciaires ni être soumise au paiement d'une avance de frais (consid. 4.4), et que l'argumentation de la Cour de droit public du Tribunal cantonal neuchâtelois tirée d'une longue pratique et d'une prétendue lacune de la loi qui devrait être comblée au moyen d'une application par analogie de l'art. 47 al. 5 LPJA, relatif à la procédure de recours, devait être écartée (consid. 4.5).
A la suite de cet arrêt, le Grand Conseil du canton de Neuchâtel a adopté le 18 février 2020, sur proposition du Conseil d'Etat du 27 novembre 2019, une loi modifiant la LPJA (Feuille officielle n° 10 du vendredi 6 mars 2020) : l'art. 60 al. 2 LPJA était modifié en ce sens qu'étaient désormais également applicables à la procédure d'action de droit administratif les art. 47 et 48 LPJA notamment (relatifs aux frais et dépens); l'art. 60 LPJA était en outre complété par un al. 3 aux termes duquel les frais et dépens sont mis à la charge de la partie qui succombe; enfin, les dispositions transitoires prévoyaient que l'art. 60 al. 2 et 3 LPJA s'applique aux procédures pendantes à l'entrée en vigueur de cette loi. Celle-ci est entrée en vigueur le 15 juin 2020.
5.2.4. Il est ainsi constant qu'au moment où les recourants ont ouvert leur action de droit administratif le 30 septembre 2016, il n'existait pas de base légale permettant de mettre des frais judiciaires ou des dépens à leur charge si leur action devait être rejetée, et qu'ils n'ont eu aucun moyen d'adapter leur comportement à la nouvelle situation légale résultant de l'adoption de la loi du 18 février 2020 modifiant la LPJA. Les dispositions transitoires de cette loi, aux termes desquelles l'art. 60 al. 2 et 3 LPJA s'applique aux procédures pendantes à l'entrée en vigueur de cette loi, ne prévoient pas de rétroactivité proprement dite, mais uniquement une rétroactivité improprement dite (cf. consid. 5.2.2 supra). Cela ne saurait en soi être reproché au législateur cantonal, au vu de l'intérêt public à ce que la nouvelle réglementation - destinée à corriger un traitement inégal selon que la Cour de droit public est saisie par voie de recours ou d'action - entre en vigueur sans retard et puisse être appliquée également aux procédures déjà pendantes au moment de son entrée en vigueur.
5.2.5. Cela étant, la décision de condamner, dans un cas particulier, une partie à payer des frais judiciaires et des dépens en application des dispositions transitoires doit respecter le principe de la bonne foi au regard du but de la loi et des circonstances du cas d'espèce. A cet égard, il y a lieu de tenir compte du fait que les frais judiciaires doivent, en tant que taxes causales, respecter notamment le principe d'équivalence, de sorte que ces frais doivent être en rapport avec la valeur objective de la prestation fournie par l'Etat et rester dans des limites raisonnables, sans avoir à correspondre strictement aux coûts induits par la procédure à laquelle ils se rapportent (ATF 145 I 52 consid. 5.2.3; 141 I 105 consid. 3.3.2; arrêt 2C_572/2019 du 11 mars 2020 consid. 6, non publié in ATF 146 I 157). Quant aux dépens, ils visent à indemniser la partie qui obtient gain de cause pour les frais (avant tout d'avocat) nécessaires causés par le litige (cf. art. 68 al. 2 LTF; art. 48 al. 1 LPJA).
En l'espèce, les recourants ont ouvert action le 30 septembre 2016 et l'échange d'écritures s'est terminé avec le dépôt de la duplique le 21 décembre 2017. Le 30 novembre 2018, à la demande du juge instructeur, l'avocate des recourants a encore déposé des tableaux explicitant pour chacun d'eux les bases de leurs prétentions pour chacune des années concernées, sur lesquels l'intimé s'est déterminé le 31 janvier 2019. Il n'y a ensuite eu aucun acte de procédure jusqu'au 28 novembre 2019, date à laquelle l'avocate des recourants a interpellé la cour cantonale sur le délai dans lequel une décision pourrait être rendue. La cour cantonale a répondu le 9 décembre 2019 qu'elle faisait de cette affaire une priorité et qu'"un arrêt devrait pouvoir être rendu dans le courant du premier trimestre 2020". La Cour de droit public a finalement rendu un arrêt daté du 17 juin 2020, qui a été envoyé le même jour aux parties.
Il s'avère ainsi que la (quasi-) totalité de l'activité déployée par l'autorité précédente l'a été avant l'entrée en vigueur le 15 juin 2020 de la modification de la LPJA du 18 février 2020, et que, mise à part la brève détermination relative aux tableaux, l'activité déployée par l'avocat de la partie adverse l'a été avant même que le Conseil d'Etat soumette au Grand Conseil cette proposition de loi le 27 novembre 2019. Par ailleurs, les recourants n'auraient pas pu se voir condamner aux frais et dépens en application des dispositions transitoires de la modification de la LPJA du 18 février 2020 si un arrêt avait été rendu dans le courant du premier trimestre 2020 comme ils en avaient été renseignés par avis du 9 décembre 2019, et ils n'ont à aucun moment eu la possibilité de prendre des dispositions pour se prémunir du risque de devoir payer des frais judiciaires et des dépens. Dans ces circonstances, leur condamnation, dans un arrêt rendu formellement deux jours après l'entrée en vigueur de la modification de la LPJA du 18 février 2020, à payer des frais judiciaires à hauteur de 66'000 fr. (cf. consid. 5.1.1 supra) ainsi que des dépens à hauteur de 40'000 fr. (cf. consid. 5.1.2 supra) contrevient au principe de la bonne foi. Elle doit par conséquent être annulée, sans qu'il y ait lieu d'examiner les griefs soulevés à titre subsidiaire par les recourants contre la quotité des frais judiciaires et des dépens mis à leur charge (cf. consid. 5.2.1 in fine supra).
6.
Il résulte de ce qui précède que le recours en matière de droit public doit être partiellement admis en ce qui concerne la condamnation des recourants à payer des frais judiciaires et des dépens pour la procédure cantonale (cf. consid. 5.2.5 supra) et rejeté pour le surplus (cf. consid. 3.4 et 4.3 supra), le recours constitutionnel subsidiaire étant quant à lui irrecevable (cf. consid. 1 supra).
Vu l'issue du litige, les frais judiciaires seront mis pour neuf dixièmes à la charge des recourants et pour un dixième à la charge de l'intimé (art. 66 al. 1 LTF). L'intimé versera aux recourants une indemnité de 3000 fr. à titre de dépens réduits (art. 68 al. 1 et 2 LTF; art. 4 du règlement du 31 mars 2006 sur les dépens alloués à la partie adverse et sur l'indemnité pour la représentation d'office dans les causes portées devant le Tribunal fédéral [RS 173.110.210.3]). Bien qu'obtenant partiellement gain de cause, l'intimé n'a pas droit à des dépens (art. 68 al. 3 LTF; arrêt 8C_70/2010 du 20 décembre 2010 consid. 8.2, non publié in ATF 137 I 58).
Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours en matière de droit public est partiellement admis. Les chiffres 2 et 3 du dispositif de l'arrêt rendu le 17 juin 2020 par la Cour de droit public du Tribunal cantonal de la République et canton de Neuchâtel sont annulés. Le recours est rejeté pour le surplus.
2.
Le recours constitutionnel subsidiaire est irrecevable.
3.
Les frais judiciaires, arrêtés à 100'000 fr., sont mis à la charge des recourants par 90'000 fr. et à la charge de l'intimé par 10'000 fr.
4.
L'intimé versera aux recourants la somme de 3000 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
5.
Le présent arrêt est communiqué aux parties et à la Cour de droit public du Tribunal cantonal de la République et canton de Neuchâtel.
Lucerne, le 24 juin 2021
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président : Maillard
La Greffière : Castella