Faits :
A.
A.a. Par lettre du 21 juillet 2010, A._, né en 1975, a été engagé par les Hôpitaux universitaires de Genève (ci-après: les HUG) en qualité de "chef de secteur B._" rattaché au département C._. Le 21 juin 2012, il a été nommé fonctionnaire avec effet au 1er septembre 2012.
A.b. Par décision du 23 novembre 2016, les HUG, sous la signature de leur directrice des ressources humaines, ont résilié les rapports de service du prénommé avec effet au 28 février 2017. Cette décision était motivée par des manquements graves et répétés aux devoirs de service de l'intéressé. Elle faisait suite à un entretien du 5 novembre 2015 dont le compte-rendu faisait état d'un non-respect des directives, d'une gestion lacunaire des collaborateurs, d'objectifs non atteints et d'un comportement inapproprié envers des collègues et des clients. L'employé s'était déterminé le 15 décembre 2015 et avait contesté les reproches formulés à son endroit, relevant qu'un licenciement serait en toute hypothèse une mesure injustifiée.
A.c. Statuant par arrêt du 20 juin 2017 sur le recours interjeté le 9 janvier 2017 par l'employé contre cette décision, la Chambre administrative de la Cour de justice de la République et canton de Genève (ci-après: la Chambre administrative) a constaté que la décision attaquée était contraire au droit, a proposé la réintégration de l'employé au sein des HUG et a ordonné à ces derniers, en cas de refus d'y procéder, de transmettre leur décision à la Chambre administrative. Par arrêt du 13 août 2018 (8C_561/2017), le Tribunal fédéral a rejeté le recours interjeté par les HUG contre cet arrêt.
A.d. Par lettre du 7 septembre 2018, les HUG ont informé la Chambre administrative de leur décision de ne pas réintégrer A._. Lors d'une audience de comparution personnelle et d'enquêtes, le juge délégué de la Chambre administrative a entendu l'employé en qualité de partie ainsi que deux témoins, soit D._, qui était la supérieure hiérarchique directe du recourant, et E._, qui était responsable des ressources humaines.
B.
Par arrêt du 10 décembre 2019, la Chambre administrative, ressaisie de la cause ensuite du refus des HUG de réintégrer l'employé, a admis partiellement le recours interjeté le 9 janvier 2017 par celui-ci contre la décision des HUG du 23 novembre 2016; elle a constaté que le licenciement était contraire au droit et a condamné les HUG à payer à A._ une indemnité correspondant à quatre mois de son dernier traitement mensuel brut.
C.
A._ interjette un recours en matière de droit public contre cet arrêt, en concluant à sa réforme en ce sens que sa réintégration soit ordonnée, subsidiairement en ce sens que les HUG soient condamnés à lui payer une indemnité correspondant à vingt-quatre mois de son dernier traitement mensuel brut. A titre plus subsidiaire, il conclut à l'annulation de l'arrêt entrepris et au renvoi de la cause à la Chambre administrative pour nouvelle décision dans le sens des considérants.
Les intimés concluent au rejet du recours, dans la mesure de sa recevabilité. La Chambre administrative a déclaré s'en remettre à justice quant à la recevabilité du recours et persister dans les considérants et le dispositif de son arrêt. Le recourant a répliqué.

Considérant en droit :
1.
1.1. L'arrêt entrepris a été rendu en matière de rapports de travail de droit public. S'agissant d'une contestation pécuniaire, le motif d'exclusion du recours en matière de droit public prévu par l'art. 83 let. g LTF ne s'applique pas. La valeur litigieuse atteint par ailleurs le seuil de 15'000 fr. ouvrant la voie du recours en matière de droit public en ce domaine (art. 51 al. 2 et 85 al. 1 let. b LTF). Interjeté en temps utile (<ref-law>) et dans les formes requises (<ref-law>) contre une décision finale (<ref-law>) prise par un tribunal supérieur statuant en dernière instance cantonale (art. 86 al. 1 let. d LTF), le recours est ainsi recevable en tant qu'il est dirigé contre l'arrêt du 10 décembre 2019.
1.2. Il sied d'examiner si le recourant peut aussi, par son recours contre l'arrêt du 10 décembre 2019, attaquer l'arrêt du 20 juin 2017 dans la mesure où celui-ci influe sur le contenu de celui-là.
Un arrêt par lequel la juridiction cantonale constate que la décision de résiliation des rapports de service d'un employé par les HUG est contraire au droit et propose la réintégration de l'employé au sein des HUG s'analyse - au moment où il est rendu - comme une décision à tout le moins potentiellement finale, dès lors que ce n'est qu'en cas de décision négative de l'employeur sur la proposition de réintégration que la Chambre administrative est ressaisie de l'affaire, conformément à l'art. 31 al. 4 LPAC (cf. consid. 3.2 infra); l'employeur peut donc recourir au Tribunal fédéral contre une telle décision (arrêt 8C_257/2019 du 12 mai 2020 consid. 1.2; cf. arrêt 8C_430/2011 du 12 avril 2012). Lorsque l'employeur refuse de réintégrer l'employé, la Chambre administrative est ressaisie de l'affaire et sa première décision apparaît a posteriori comme une décision incidente (cf. arrêt 8C_561/2017 du 13 août 2018 consid. 2.3). L'employé - qui n'aurait pas eu d'intérêt digne de protection à l'annulation ou à la modification de la première décision (art. 89 al. 1 let. c LTF) - peut donc recourir contre la décision finale et, par ce recours, attaquer également la précédente décision dans la mesure où elle influe sur le contenu de la décision finale (<ref-law>). En l'espèce, le recourant peut donc aussi, par son recours contre l'arrêt du 10 décembre 2019, attaquer l'arrêt du 20 juin 2017 dans la mesure où celui-ci influe sur le contenu de celui-là (cf. consid. 5 infra).
2.
2.1. Le Tribunal fédéral, qui est un juge du droit, fonde son raisonnement juridique sur les faits retenus par l'autorité précédente (<ref-law>), sauf s'ils ont été établis de façon manifestement inexacte - notion qui correspond à celle d'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 2 p. 190) - ou en violation du droit au sens de l'<ref-law> (cf. <ref-law>). Si le recourant entend s'écarter des constatations de fait de l'autorité précédente, il doit expliquer de manière circonstanciée en quoi les conditions de l'<ref-law> seraient réalisées et la correction du vice susceptible d'influer sur le sort de la cause (<ref-law>); à défaut, un état de fait divergent de celui de la décision attaquée ne peut pas être pris en compte (<ref-ruling> consid. 2 précité; <ref-ruling> consid. 5.2.2 p. 322). Le Tribunal fédéral n'entre pas en matière sur des critiques appellatoires portant sur l'appréciation des preuves ou l'établissement des faits par l'autorité précédente (<ref-ruling> consid. 2 p. 215; <ref-ruling> consid. 2.3 p. 266). L'appréciation des preuves est arbitraire lorsqu'elle est manifestement insoutenable, en contradiction avec le dossier, ou lorsque l'autorité ne tient pas compte, sans raison sérieuse, d'un élément propre à modifier la décision, se trompe sur le sens et la portée de celui-ci ou, se fondant sur les éléments recueillis, en tire des conclusions insoutenables (ATF <ref-ruling> consid. 2.3 précité et les références).
2.2. Le Tribunal fédéral applique le droit d'office (<ref-law>). 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 (<ref-law>). 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 (<ref-law> 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'<ref-law> (<ref-ruling> consid. 3.2 p. 579 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 (<ref-ruling> consid. 7.1 p. 124 et la référence).
3.
Il est constant qu'en tant que membre du personnel des HUG, le recourant est soumis à la loi générale du 4 décembre 1997 relative au personnel de l'administration cantonale, du pouvoir judiciaire et des établissements publics médicaux (LPAC; RS/GE B 5 05), au règlement d'application de cette loi, du 24 février 1999 (RPAC; RS/GE B 5 05.01) ainsi qu'au Statut du personnel des HUG du 16 décembre 1999 (ci-après: le Statut).
3.1. Selon l'art. 21 al. 3 LPAC, l'autorité compétente peut résilier les rapports de service du fonctionnaire pour un motif fondé; elle motive sa décision; elle est tenue, préalablement à la résiliation, de proposer des mesures de développement et de réinsertion professionnels et de rechercher si un autre poste au sein de l'administration cantonale correspond aux capacités de l'intéressé; les modalités sont fixées par règlement. Aux termes de l'art. 22 LPAC, il y a motif fondé lorsque la continuation des rapports de service n'est plus compatible avec le bon fonctionnement de l'administration, soit notamment en raison de l'insuffisance des prestations (let. a), de l'inaptitude à remplir les exigences du poste (let. b) ou de la disparition durable d'un motif d'engagement (let. c).
Les membres du personnel des HUG sont tenus au respect de l'intérêt de l'établissement et doivent s'abstenir de tout ce qui peut lui porter préjudice (art. 20 du Statut). Ils se doivent, par leur attitude, d'entretenir des relations dignes et correctes avec leurs supérieurs, leurs collègues et leurs subordonnés, et de permettre et de faciliter la collaboration entre ces personnes (art. 21 let. a du Statut). S'agissant de l'exécution du travail, les membres du personnel se doivent de remplir tous les devoirs de leur fonction consciencieusement et avec diligence (art. 22 al. 1 du Statut). Les membres du personnel chargés de fonctions d'autorité sont tenus, en outre, notamment d'organiser le travail de leur service, de diriger leurs subordonnés, d'en coordonner et contrôler l'activité et d'assurer l'exécution ou la transmission des décisions qui leur sont notifiées (art. 23 du Statut).
3.2. Aux termes de l'art. 31 LPAC, tout membre du personnel dont les rapports de service ont été résiliés peut recourir à la chambre administrative pour violation de la loi (al. 1). Si la chambre administrative retient que la résiliation des rapports de service ne repose pas sur un motif fondé, elle ordonne à l'autorité compétente la réintégration (al. 2). Si la chambre administrative retient que la résiliation des rapports de service est contraire au droit, elle peut proposer à l'autorité compétente la réintégration (al. 3). En cas de décision négative de celle-ci ou de refus du recourant, la chambre administrative fixe une indemnité dont le montant ne peut pas être inférieur à un mois et supérieur à vingt-quatre mois du dernier traitement brut à l'exclusion de tout autre élément de rémunération; concernant un employé, l'indemnité ne peut pas être supérieure à six mois (al. 4).
4.
4.1. Au considérant 3 de son arrêt du 10 décembre 2019, la Chambre administrative a rappelé que dans son précédent arrêt du 20 juin 2017, elle avait constaté que la décision de résiliation n'était pas nulle mais était contraire au droit au sens de l'art. 31 al. 3 LPAC car prononcée par une autorité incompétente; en conséquence, elle avait proposé la réintégration du recourant au sein des HUG en application de cette même disposition légale. Dès lors que les HUG avaient refusé la réintégration du recourant le 7 septembre 2018, la Chambre administrative était toujours saisie du recours déposé contre la décision de résiliation. Contrairement à ce que soutenait le recourant, les HUG à qui la proposition de réintégration avait été faite avaient, par leur refus, confirmé la décision de résiliation prise initialement par la directrice générale des ressources humaines.
Cela étant, les juges cantonaux ont considéré qu'il leur restait à examiner si la décision de résiliation avait été prise dans le respect du droit d'être entendu du recourant (consid. 5 de l'arrêt du 10 décembre 2019), si elle avait été prononcée pour des motifs fondés au sens de l'art. 22 LPAC (consid. 6 et 7 dudit arrêt), si elle avait été rendue en conformité avec la procédure prévue par la LPAC et le RPAC (consid. 8 dudit arrêt) et, le cas échéant, à fixer une indemnité au sens de l'art. 31 al. 3 LPAC (consid. 9 dudit arrêt).
4.2. Il y a lieu d'examiner ci-après tout d'abord les griefs soulevés par le recourant en relation avec la prétendue nullité absolue de la décision de licenciement (cf. consid. 5 infra), puis ceux relatifs à la question de sa réintégration au sein des HUG (cf. consid. 6 infra), puis les griefs relatifs au respect par les HUG de son droit d'être entendu (cf. consid. 7 infra), puis les griefs d'ordre formel soulevés en relation avec la procédure devant la cour cantonale (cf. consid. 8 infra), puis ceux dirigés contre l'établissement des faits par la cour cantonale (cf. consid. 9 infra), et enfin ses griefs relatifs à l'indemnité qui lui est due en application de l'art. 31 al. 4 LPAC (cf. consid. 10 infra).
5.
5.1. Dans son arrêt du 20 juin 2017, la Chambre administrative a exposé que le conseil d'administration des HUG était l'autorité compétente pour prononcer la fin des rapports de service des fonctionnaires. Elle a constaté que si l'art. 17 al. 4 LPAC autorisait le conseil d'administration à déléguer à la direction générale la compétence de prononcer la fin des rapports de service, une sous-délégation en faveur des services de l'établissement - en l'occurrence la direction des ressources humaines - n'était possible qu'en ce qui concernait les employés qui n'avaient pas le statut de fonctionnaire. La cour cantonale a ainsi conclu que l'art. 5 ch. 3 du règlement des HUG du 5 octobre 2000 relatif à la répartition des compétences en matière de gestion du personnel (ci-après: le règlement) était contraire à la loi dans la mesure où il conférait à la direction des ressources humaines le pouvoir de décider de l'engagement et du licenciement de toutes les catégories de personnel non citées dans les précédents articles, sans opérer de distinction en fonction de leur statut (employés ou fonctionnaires). Comme le recourant avait le statut de fonctionnaire à la date de son licenciement, celui-ci avait donc été prononcé par une autorité incompétente, et partant, d'une manière contraire au droit. Examinant ensuite la sanction à attacher à ce vice formel, les juges cantonaux ont considéré que si le vice en cause était grave dans la mesure où il concernait l'incompétence de l'autorité ayant rendu la décision, il ne pouvait cependant pas être qualifié de manifeste, ni même de facilement décelable, vu les particularités de l'organisation des HUG examinées précédemment sur plusieurs pages et notamment le fait que la directrice des ressources humaines faisait partie du comité de direction. Les conditions de constatation de la nullité n'étaient ainsi pas remplies, de sorte que la décision de licenciement n'était pas nulle de plein droit, mais seulement contraire au droit.
5.2. Le recourant reproche à l'autorité cantonale d'avoir violé son droit d'être entendu, sous l'angle de son droit à ce que sa cause soit traitée par une autorité compétente, en considérant dans son arrêt du 20 juin 2017 que la décision de licenciement du 23 novembre 2016, prise par une autorité incompétente, n'était pas nulle de plein droit mais seulement contraire au droit. A cet égard, le recourant se plaint également d'une violation de l'égalité de traitement et de l'interdiction de l'arbitraire, en se référant à d'autres arrêts dans lesquels la Chambre administrative aurait admis la nullité absolue d'une décision de licenciement prise par une autorité incompétente.
5.3. Selon la jurisprudence du Tribunal fédéral, la nullité absolue d'une décision, qui peut être invoquée en tout temps devant toute autorité et doit être constatée d'office, ne frappe que les décisions affectées des vices les plus graves, manifestes ou du moins facilement décelables, et pour autant que la constatation de la nullité ne mette pas sérieusement en danger la sécurité du droit. Hormis dans les cas expressément prévus par la loi, il n'y a lieu d'admettre la nullité qu'à titre exceptionnel, lorsque les circonstances sont telles que le système d'annulabilité n'offre manifestement pas la protection nécessaire. Des vices de fond n'entraînent qu'à de rares exceptions la nullité d'une décision; de graves vices de procédure, ainsi que l'incompétence qualifiée de l'autorité qui a rendu la décision, sont des motifs de nullité (<ref-ruling> consid. 4 p. 438; <ref-ruling> consid. 1.4.3 p. 368; <ref-ruling> consid. 11.2 p. 260; <ref-ruling> consid. 3.1 p. 503 et les références; arrêt 1C_281/2018 du 12 septembre 2019 consid. 3.1).
5.4. Le recourant ne démontre pas en quoi l'autorité cantonale aurait considéré de manière arbitraire (cf. consid. 2.2 supra) que les conditions d'une constatation de la nullité absolue de la décision de licenciement prise par la directrice des ressources humaines n'étaient pas remplies, se contentant à cet égard d'opposer sa propre appréciation à celle des juges cantonaux. On ne voit en particulier pas en quoi il serait arbitraire de considérer qu'on n'était pas en présence d'une incompétence qualifiée, manifeste ou du moins facilement décelable: en effet, la cour cantonale a dû procéder sur de nombreuses pages à un examen détaillé des lois et réglementations cantonales topiques, nécessitant le recours aux travaux préparatoires, pour parvenir au constat que l'art. 5 ch. 3 du règlement était contraire à la loi et que la décision de licenciement litigieuse avait ainsi été signée par une autorité incompétente. L'arrêt de la Chambre administrative ATA/312/2015 du 31 mars 2015 invoqué par le recourant, dans lequel cette autorité avait constaté la nullité d'une décision de révocation prise par le seul bureau du conseil d'administration des HUG, ne lui est d'aucun secours dans la mesure où il visait une situation très différente. En effet, dans cet arrêt, la Chambre administrative avait expressément relevé que la constatation de la nullité ne mettait pas sérieusement en danger la sécurité du droit dans la mesure où l'intéressé demeurait fonctionnaire, suspendu sans traitement - en vertu d'une décision de suspension non viciée - dans l'attente d'une décision de révocation qui pourrait cette fois-ci être prise par l'autorité dans sa correcte composition. Or il en va différemment en l'espèce, où le constat de la nullité de la décision de licenciement contraindrait les intimés, plus de trois ans après le licenciement du recourant et alors que son poste a été repourvu, à le reprendre à leur service et à lui verser les arriérés de traitement. De même, c'est en vain que le recourant se plaint d'une violation de l'égalité de traitement et de l'interdiction de l'arbitraire: en effet, les arrêts de la Chambre administrative qu'il invoque à l'appui de ce grief tranchent soit des cas où la cour a nié la nullité de plein droit d'un licenciement prononcé par une autorité incompétente, soit des cas - essentiellement dans des domaines autres que la fonction publique - où l'incompétence était manifeste.
6.
6.1.
6.1.1. Le recourant reproche à l'autorité cantonale d'avoir violé son droit d'être entendu ainsi que l'interdiction du déni de justice formel en s'abstenant de statuer sur la question de sa réintégration, expressément soulevée par lui, au motif que les HUG s'étaient déjà prononcés sur leur volonté de ne pas le réintégrer.
6.1.2. Selon la jurisprudence, l'autorité qui ne traite pas un grief relevant de sa compétence, motivé de façon suffisante et pertinent pour l'issue du litige, commet un déni de justice formel proscrit par l'art. 29 al. 1 Cst. (<ref-ruling> consid. 2.1 p. 9; <ref-ruling> consid. 2.3 p. 232; <ref-ruling> consid. 3a p. 117 et les références), ce qu'il appartient au recourant d'établir (<ref-ruling> consid. 3 p. 246; arrêt 5A_710/2016 du 2 mars 2017 consid. 3.1).
6.1.3. La jurisprudence a déduit du droit d'être entendu garanti par l'art. 29 al. 2 Cst. l'obligation pour l'autorité de motiver sa décision, afin que l'intéressé puisse se rendre compte de la portée de celle-ci et exercer son droit de recours à bon escient (<ref-ruling> consid. 2.1 p. 145; <ref-ruling> consid. 5.1 p. 237; <ref-ruling> consid. 4.2 p. 355). Pour satisfaire à ces exigences, il suffit que l'autorité mentionne, au moins brièvement, les motifs qui l'ont guidée et sur lesquels elle a fondé son raisonnement. Elle ne doit pas se prononcer sur tous les moyens des parties, mais peut au contraire se limiter aux questions décisives (<ref-ruling> consid. 5.2 p. 70 s.; <ref-ruling> consid. 4.2 p. 157; <ref-ruling> consid. 3.2 p. 270; <ref-ruling> consid. 5.2 p. 236). La motivation peut d'ailleurs être implicite et résulter des différents considérants de la décision (<ref-ruling> consid. 3.2.1 p. 565).
6.1.4. En l'espèce, on peine à distinguer, dans l'argumentation confuse du recourant, en quoi l'autorité cantonale aurait violé l'art. 29 Cst. En effet, en ce qui concerne les motifs avancés par le recourant à l'appui de sa conclusion en réintégration, la cour cantonale s'est dûment prononcée sur la prétendue nullité de la décision de licenciement pour cause d'incompétence ainsi que sur les griefs de violation de son droit d'être entendu. Elle a par ailleurs exposé que la constatation selon laquelle la résiliation des rapports de service était contraire au droit ne pouvait déboucher que sur une proposition de réintégration, en l'occurrence refusée par les intimés. Enfin, elle a examiné si la résiliation des rapports de service reposait sur des motifs fondés et a constaté que tel était le cas, si bien qu'une réintégration fondée sur l'art. 31 al. 2 LPAC n'entrait pas en considération. Le grief de violation de l'art. 29 Cst. tombe ainsi à faux.
6.2.
6.2.1. Le recourant reproche en outre à l'autorité cantonale d'avoir fait une application arbitraire de l'art. 31 al. 2 et 3 LPAC, respectivement de n'avoir pas constaté l'inconstitutionnalité de l'art. 31 al. 3 LPAC, "en tant qu'il permettrait au maire d'une commune de faire signer à son cantonnier une décision de licenciement pour pouvoir s'assurer de pouvoir contourner l'obligation de réintégration du fonctionnaire". Selon le recourant, le mécanisme prévu à l'art. 31 al. 2 à 4 LPAC consacrerait de fait une violation du principe de l'égalité de traitement (art. 8 Cst.), le fonctionnaire licencié sans motif fondé dont les droits procéduraux ont été respectés se retrouvant dans une posture plus favorable à celui licencié sans motif fondé en violation de ses droits procéduraux. Un tel mécanisme serait également arbitraire (art. 9 Cst.) et violerait le droit d'être entendu (art. 29 al. 2 Cst.) en tant qu'il pourrait permettre à l'autorité de se retrouver dans une situation plus avantageuse en violant les droits procéduraux d'un fonctionnaire plutôt qu'en les respectant.
6.2.2. Par cette argumentation, le recourant ne démontre ni en quoi l'autorité cantonale aurait fait une application arbitraire de l'art. 31 LPAC, ni en quoi cette disposition serait en elle-même inconstitutionnelle. La distinction opérée par la loi entre d'une part le licenciement fondé mais prononcé en violation des règles de procédure, qui ne peut entraîner qu'une proposition de réintégration avec le versement d'une indemnité en cas de refus de l'employeur, et d'autre part le licenciement fondé, qui donne lieu à une réintégration obligatoire, a été voulue par le législateur cantonal (cf. arrêt 8C_203/2020 du 25 août 2020 consid. 3.3.2) et n'apparaît pas contraire à l'égalité de traitement en tant qu'elle permet de traiter de manière différente des situations dissemblables (cf. <ref-ruling> consid. 6.2.3 p. 145 s.; <ref-ruling> consid. 3.6.1 p. 229 s. et les références). Par ailleurs, il n'apparaît pas qu'une telle réglementation permettrait en définitive à l'employeur public de se retrouver dans une situation plus avantageuse en violant les droits procéduraux d'un fonctionnaire plutôt qu'en les respectant. En effet, si le licenciement ne repose pas sur des motifs fondés, le fonctionnaire peut obtenir sa réintégration indépendamment d'une éventuelle violation de ses droits procéduraux donnant lieu, comme en l'espèce, à une première décision de la Chambre administrative fondée sur l'art. 31 al. 3 LPAC.
7.
7.1. Examinant les griefs du recourant en lien avec les violations alléguées de son droit d'être entendu par les intimés, la cour cantonale a d'abord considéré que le recourant ne pouvait pas se plaindre de n'avoir pas été "interpellé" avant le licenciement qui avait eu lieu près d'une année après qu'il avait eu l'occasion de se prononcer sur les divers reproches formulés à son encontre. En effet, dès lors qu'il admettait lui-même avoir eu l'occasion de déposer des observations circonstanciées après l'entretien de service lors duquel des manquements graves et répétés aux devoirs de service avaient été relevés, et que la décision de résiliation se fondait précisément sur ces manquements, son droit d'être entendu avait été respecté. Quant à "l'offre de preuve" faite par le recourant aux HUG, les juges cantonaux ont relevé qu'elle portait sur l'un des éléments qui lui étaient reprochés, soit le dépassement des heures supplémentaires faites par les collaborateurs de son secteur. Or, même à supposer que le recourant ait fourni la preuve recherchée, les autres manquements évoqués lors de l'entretien de service auraient été suffisants pour constituer un motif fondé. Enfin, la cour cantonale a considéré que la motivation de la décision était suffisante puisqu'elle renvoyait à l'entretien de service du 5 novembre 2015, lequel avait été suivi le 10 novembre 2015 d'un compte-rendu détaillant sur près de sept pages avec des pièces annexées les manquements reprochés ainsi que les articles du Statut auxquels ils se rapportaient. Pour le surplus, le recourant avait manifestement compris les motifs à l'origine de son licenciement, à propos desquels il avait pu prendre position à de nombreuses reprises, notamment dans sa détermination du 15 décembre 2015 détaillée sur vingt-quatre pages, avant le prononcé du licenciement.
7.2.
7.2.1. Le recourant reproche à l'autorité cantonale d'avoir violé l'art. 29 al. 2 Cst. en considérant que les HUG avaient respecté son droit de s'exprimer avant que la décision de licenciement du 23 novembre 2016 soit prise.
7.2.2. Selon l'art. 29 al. 2 Cst., les parties ont le droit d'être entendues. Ce droit sert non seulement à établir correctement les faits, mais constitue également un droit indissociable de la personnalité garantissant à un particulier de participer à la prise d'une décision qui touche sa position juridique (<ref-ruling> consid. 3.2 p. 282; <ref-ruling> consid. 3.2 p. 494 et les références; arrêt 8C_37/2020 du 7 septembre 2020 consid. 3.1). L'étendue du droit de s'exprimer ne peut pas être déterminée de manière générale, mais doit être définie au regard des intérêts concrètement en jeu; l'idée maîtresse est qu'il faut permettre à une partie de pouvoir mettre en évidence son point de vue de manière efficace (<ref-ruling> consid. 5.3 p. 17 s. et les arrêts cités). En matière de rapports de travail de droit public, la jurisprudence admet que des occasions relativement informelles de s'exprimer avant le licenciement peuvent remplir les exigences du droit constitutionnel d'être entendu, pour autant que la personne concernée ait compris qu'une telle mesure pouvait entrer en ligne de compte à son encontre (<ref-ruling> consid. 5.3 p. 18 in fine). La personne concernée ne doit pas seulement connaître les faits qui lui sont reprochés, mais doit également savoir qu'une décision allant dans une certaine direction est envisagée à son égard (arrêt 8C_158/2009 du 2 septembre 2009 consid. 5.2, non publié aux <ref-ruling>, et les arrêts cités).
7.2.3. En l'espèce, comme la cour cantonale l'a constaté à juste titre, le droit d'être entendu du recourant a été respecté, dès lors que celui-ci a eu l'occasion de déposer des observations circonstanciées après l'entretien de service lors duquel des manquements graves et répétés aux devoirs de service avaient été relevés et qu'il savait qu'une décision de licenciement était envisagée à son égard. Le recourant ne saurait déduire un droit d'être "interpellé" une nouvelle fois du fait que le licenciement a été prononcé - en raison notamment de la procédure de reclassement - près d'une année après qu'il s'était déterminé sur les reproches formulés à son encontre.
7.3.
7.3.1. Le recourant reproche à l'autorité cantonale d'avoir violé l'art. 29 al. 2 Cst. en considérant que la décision de licenciement du 23 novembre 2016 était suffisamment motivée.
7.3.2. Force est toutefois de constater, pour les motifs exposés dans le jugement attaqué et auxquels il peut être renvoyé, que la motivation de la décision de licenciement se révèle suffisante au regard de l'obligation pour l'autorité de motiver sa décision, telle qu'elle est circonscrite par la jurisprudence déjà exposée (cf. consid. 6.1.3). Le seul fait que les déterminations du recourant quant aux reproches formulés à son encontre n'aient pas été expressément discutées dans la décision ne saurait conduire à considérer la motivation de celle-ci comme insuffisante, d'autant moins que le recourant a manifestement été en mesure de l'attaquer en connaissance de cause.
8.
8.1. Se prononçant sur les requêtes du recourant tendant à la production de plusieurs documents par les intimés, la cour cantonale a considéré que ni l'intégralité du rapport d'audit du service propreté et hygiène de juillet 2013, ni celle des procès-verbaux y afférents, ou encore un courrier de démission particulier, de surcroît envoyé après l'entretien de service du recourant, n'étaient nécessaires pour trancher le litige. Les juges cantonaux ont en outre considéré que l'audition de témoins supplémentaires, telle que requise par le recourant, n'était pas susceptible de modifier l'issue du litige. En effet, il ressortait du dossier que le recourant n'arrivait pas à effectuer ses tâches de chef de secteur à la satisfaction de son employeur et en particulier de sa hiérarchie directe, et cette constatation ne pourrait pas être remise en cause par l'audition de témoins, collègues ou collaborateurs, telle que proposée par le recourant.
8.2.
8.2.1. Le recourant reproche à l'autorité cantonale d'avoir violé son droit d'être entendu, sous l'angle du droit à la réplique, pour ne lui avoir jamais remis un courrier de démission - daté du 9 mai 2014 et provenant d'un collaborateur qui mettait sa décision en lien avec l'attitude du recourant, lequel était son responsable hiérarchique - que E._, entendu comme témoin le 5 février 2019, avait communiqué à la cour à l'issue de son audition.
8.2.2. Compris comme l'un des aspects de la notion générale de procès équitable, le droit d'être entendu, tel qu'il est garanti par les art. 29 al. 2 Cst. et 6 CEDH, comprend en particulier le droit, pour une partie à un procès, de prendre connaissance de toute argumentation présentée au tribunal et de se déterminer à son propos, que celle-ci contienne ou non de nouveaux éléments de fait ou de droit, et qu'elle soit ou non concrètement susceptible d'influer sur le jugement à rendre. Il appartient en effet aux parties, et non au juge, de décider si une prise de position ou une pièce nouvellement versée au dossier contient des éléments déterminants qui appellent des observations de leur part (<ref-ruling> consid. 3.4.1 p. 103 s.; <ref-ruling> consid. 4.1.1; <ref-ruling> consid. 3.2; <ref-ruling> consid. 2.1; <ref-ruling> consid. 2).
8.2.3. En l'espèce, la Chambre administrative a indiqué dans son arrêt que le courrier de démission en question, de surcroît envoyé après l'entretien de service du recourant, n'était pas nécessaire pour trancher le litige. En d'autres termes, elle a considéré que ce courrier - remis non par une partie mais par un témoin, en dehors de toute réquisition de production de pièces - ne devait pas être versé au dossier sur la base duquel elle devait trancher. Dans ces conditions, elle n'avait pas à le communiquer au recourant et le grief doit être rejeté.
8.3.
8.3.1. Le recourant reproche à l'autorité cantonale une violation de son droit d'être entendu et de l'interdiction du déni de justice formel du fait que l'arrêt attaqué serait muet sur le point de savoir à quel titre D._ et E._ ont été entendus lors de l'audience d'instruction du 5 février 2019. Or, alors que le recourant avait soutenu lors de cette audience que les précités devaient être entendus en qualité de personnes appelées à donner des renseignements au motif qu'ils occupaient une fonction de cadres, soit de facto d'organes, la cour les avait entendus selon la forme applicable aux témoins tout en précisant qu'elle apprécierait ultérieurement à quel titre ils étaient entendus.
8.3.2. Il résulte de l'état de fait du jugement attaqué que la cour cantonale a retenu que D._ et E._ devaient bel et bien être entendus à titre de témoins. Elle a ainsi considéré implicitement que les intéressés - dont le jugement précise que la première était la supérieure hiérarchique directe du recourant tandis que le second était responsable des ressources humaines - n'étaient pas de facto des organes des HUG. Il est d'ailleurs constant qu'ils ne sont pas membres de la direction des HUG et que la décision de licenciement a été prise par la directrice des ressources humaines des HUG. Le grief doit par conséquent être rejeté.
8.4.
8.4.1. Le recourant fait grief à l'autorité cantonale d'avoir procédé à une appréciation anticipée arbitraire des preuves et violé l'interdiction du déni de justice formel en rejetant ses offres de preuve pour le motif qu'elles ne lui seraient pas utiles pour statuer.
8.4.2. Le droit de faire administrer des preuves sur des faits pertinents, tel que la jurisprudence l'a déduit du droit d'être entendu (art. 29 al. 2 Cst.), n'empêche pas l'autorité de mettre un terme à l'instruction lorsque les preuves administrées lui ont permis de former sa conviction et que, procédant d'une manière non arbitraire à une appréciation anticipée des preuves qui lui sont encore proposées, elle a la certitude que ces dernières ne pourraient pas l'amener à modifier son opinion (<ref-ruling> consid. 4.1 p. 171; <ref-ruling> consid. 6.3.1 p. 299 et les arrêts cités). Le refus d'une mesure probatoire par appréciation anticipée des preuves ne peut être remis en cause devant le Tribunal fédéral qu'en invoquant l'arbitraire (art. 9 Cst.) de manière claire et détaillée (<ref-law>; arrêt 8C_159/2018 du 17 décembre 2018 consid. 3.2 et les références).
8.4.3. En l'espèce, le recourant ne démontre pas le caractère arbitraire de l'appréciation anticipée des preuves ayant conduit la cour cantonale à rejeter ses offres de preuve supplémentaires. Il n'apparaît en particulier pas insoutenable de considérer que les auditions de F._ (collaborateur direct du recourant qui occupait un poste similaire), de G._ (qui avait procédé au coaching en 2015) et de H._ (l'une des personnes envers lesquelles le recourant avait eu une attitude problématique) n'auraient rien pu changer à la conviction acquise par les juges cantonaux, sur la base des pièces du dossier et des témoignages de D._ et de E._, que les manquements graves et répétés invoqués par les intimés à l'appui de la décision de licenciement étaient avérés. De même, l'autorité cantonale pouvait considérer sans arbitraire que la production d'un organigramme des intimés était impropre à démontrer la prétendue position d'organes de facto de ces deux témoins, et que la production des relevés d'heures supplémentaires n'était pas nécessaire dans la mesure où les autres manquements invoqués lors de l'entretien de service étaient suffisants pour fonder un licenciement. Le grief doit dès lors être rejeté.
9.
9.1. La Chambre administrative a rappelé que les HUG avaient reproché au recourant des manquements graves et répétés, détaillés dans le compte-rendu de l'entretien de service. Ces manquements découlaient notamment de courriers émanant du syndicat SSP/VPOD faisant état de dysfonctionnements, soit du manque de respect envers le personnel, de la mauvaise gestion du personnel, d'inégalité dans le traitement des collaborateurs, d'arbitraire, d'atteinte à la personnalité des collaborateurs, de non-respect des directives et règles des HUG et d'absence de soutien des collaborateurs en cas de problèmes avec le personnel soignant. Les plaintes portaient sur les cas de six personnes, représentant environ 10 % de l'équipe gérée par le recourant.
L'autorité cantonale a tenu pour établi que les reproches retenus avaient été formulés sur la base de constatations faites par la supérieure hiérarchique du recourant et qu'il y avait selon le témoignage du responsable RH du département une concordance entre ces évaluations faites par la cheffe de service et les courriers de plainte du syndicat. La plupart des plaintes dataient de 2013, mais, si un premier coaching avait mené à une certaine amélioration, constatée dans l'entretien d'évaluation du 19 février 2014, le dernier coaching de début 2015 n'avait pas pu améliorer la situation, comme en attestait l'intervention du syndicat lors d'une séance d'une commission paritaire du 5 février 2015 mettant en cause le recourant et relevant notamment des comportements inadéquats d'humiliation et de mépris du personnel. Outre les dysfonctionnements relevés ci-dessus, les manquements évoqués lors de l'entretien de service concernaient également et surtout les objectifs 2015 fixés par la cheffe de service, soit ceux portant sur la gestion des chefs d'équipe, l'organisation du secteur, le non-respect de directives et le non-respect de la loi sur le travail.
Les juges cantonaux ont relevé que le recourant, qui s'était déterminé sur tous les points évoqués, estimait principalement que beaucoup de dysfonctionnements, non contestés, n'étaient pas de sa responsabilité, mais de celle des chefs d'équipe ou de sa supérieure hiérarchique; il invoquait également que certaines tâches étaient trop nombreuses et complexes, s'agissant par exemple de saisies incomplètes. Toutefois, il ressortait du dossier que le recourant n'arrivait pas à effectuer ses tâches de chef de secteur à la satisfaction de son employeur et en particulier de sa hiérarchie directe. Alors qu'en qualité de chef de secteur, il devait être à même de gérer des chefs d'équipe et des collaborateurs, il n'avait jamais réussi à prendre en compte les problématiques de ses collaborateurs et les demandes formulées par le biais du syndicat, se contentant d'imposer des décisions et un cadre de travail à ses collaborateurs. Il s'avérait ainsi que cette façon de gérer son secteur n'était pas conforme à celle voulue par sa hiérarchie qui lui avait fixé des objectifs à cet effet, et créait les problèmes relevés par le syndicat. Les mesures mises en place pour l'aider à atteindre ses objectifs, soit les deux coachings successifs, l'un individuel et l'autre individuel et collectif, ainsi qu'une assistance administrative notamment, s'étaient révélées vaines. Force était selon les juges cantonaux de constater que dans de telles circonstances, la poursuite des rapports de service n'était pas compatible avec le bon fonctionnement du service des HUG dans lequel travaillait le recourant. La répétition sur une longue période d'actes incompatibles avec la poursuite des relations de service ayant rompu la confiance minimale nécessaire à leur exercice, la résiliation litigieuse reposait sur des motifs fondés au sens des art. 21 al. 3 et 22 LPAC.
9.2.
9.2.1. Le recourant reproche à l'autorité cantonale d'avoir violé arbitrairement l'art. 19 de la loi genevoise sur la procédure administrative du 12 septembre 1985 (LPA; RS/GE E 5 10), selon lequel le juge établit les faits d'office, en s'abstenant d'instruire sur sa situation personnelle, en particulier sur les conséquences du licenciement et sur le fait qu'il ait retrouvé un emploi, alors que ces éléments seraient centraux dans la détermination de l'indemnité fixée en application de l'art. 31 al. 4 LPAC.
9.2.2. La procédure administrative est certes régie essentiellement par la maxime inquisitoire, selon laquelle l'autorité définit les faits pertinents et les preuves nécessaires, qu'elle ordonne et apprécie d'office; cette maxime doit cependant être relativisée par son corollaire, à savoir le devoir des parties de collaborer à l'établissement des faits (<ref-ruling> consid. 5.2 p. 185 et la référence). Conformément au principe général de procédure consacré à l'<ref-law>, il incombe en effet à l'administré d'établir les faits qui sont de nature à lui procurer un avantage, spécialement lorsqu'il s'agit d'élucider des faits qu'il est le mieux à même de connaître (cf. ATF <ref-ruling> consid. 6.3.1 p. 298 s.; arrêt 1C_205/2012 du 6 novembre 2012 consid. 2.1 et les références).
9.2.3. En l'espèce, en application de ces principes, il appartenait au recourant d'établir les conséquences de son licenciement et le fait qu'il ait retrouvé un emploi s'il estimait que ces éléments relevant de sa situation personnelle étaient pertinents dans la détermination de l'indemnité qui devait être fixée ensuite du refus des HUG de le réintégrer. Il en va d'autant plus ainsi que le recourant n'évoque à cet égard aucune autre mesure d'instruction qu'une audience de comparution personnelle et qu'il aurait eu tout loisir d'évoquer sa situation lors de l'audience de comparution personnelle du 5 février 2019.
9.3.
9.3.1. Le recourant reproche à l'autorité cantonale un établissement arbitrairement incomplet des faits sur la question de son déménagement en avril 2016 dans un bureau sur le site I._, qui aurait entraîné son isolement et une dépression, ainsi que sur sa situation personnelle, tous éléments qui seraient selon lui propres à influer sur la fixation de l'indemnité qui lui est due en application de l'art. 31 al. 4 LPAC.
9.3.2. On ne voit toutefois pas, et le recourant n'explique pas, en quoi le déménagement de bureau effectué en avril 2016, dûment constaté dans l'arrêt attaqué, ou la dépression alléguée lors de l'audience de comparution personnelle du 5 février 2019 - soit plus de deux ans après le dépôt de recours et sans que cette allégation soit étayée par la production de certificats médicaux - seraient pertinents pour la fixation de l'indemnité. Quant à la situation personnelle, il peut être renvoyé à ce qui a été dit plus haut (cf. consid. 9.2.3 supra).
9.4.
9.4.1. Le recourant reproche à la cour cantonale d'avoir établi les faits de manière arbitraire et violé son droit d'être entendu, sous l'angle du défaut de motivation, en tenant pour avérés les griefs retenus à son encontre dans le compte-rendu de l'entretien du 5 novembre 2015, sans opérer aucune critique des arguments qu'il avait soulevés à leur sujet.
9.4.2. Il appert toutefois que les juges cantonaux ont procédé - en conformité avec l'obligation de motivation déduite de l'art. 29 al. 2 Cst. (cf. consid. 6.1.3 supra) - à une analyse des différents manquements reprochés au recourant selon le compte-rendu de l'entretien de service du 10 novembre 2015 pour retenir, à la lumière des pièces du dossier, des enquêtes et des observations et écritures du recourant, que ces manquements étaient avérés. Le recourant ne démontre pas en quoi l'appréciation des preuves ainsi opérée par la cour cantonale serait insoutenable (cf. consid. 2.1 supra). Il se contente essentiellement d'énumérer certains éléments qui n'auraient selon lui pas été suffisamment pris en compte, comme un contexte tendu d'après-grève qui expliquerait les courriers des syndicats, son évaluation du 19 février 2014 qui relevait qu'il avait su faire face aux attaques du syndicat sans se décourager, sa promotion le 28 février 2014 au rang de chef de secteur, les mesures organisationnelles qu'il avait prises ou encore les résultats de l'enquête de satisfaction 2015 de son secteur. Or les différents éléments en question ont été pris en compte par les juges cantonaux, comme le montre l'exposé dans l'arrêt du résultat des enquêtes - abordant ces différents points - sur lequel il se sont entre autres fondés.
10.
10.1. Ayant constaté que la procédure de reclassement n'avait pas été conforme aux exigences de la LPAC et que la résiliation des rapports de service était de ce fait contraire au droit au sens de l'art. 31 al. 3 LPAC, les juges cantonaux ont exposé qu'il convenait de fixer une indemnité au sens de l'art. 31 al. 4 LPAC qui tiendrait également compte de l'autre violation de procédure déjà constatée par l'arrêt du 20 juin 2017. Ils ont estimé qu'au vu de l'ensemble des circonstances, en particulier de l'existence de motifs fondés et de la durée des rapports de service de plus de six ans, cette indemnité devait être arrêtée à quatre mois du dernier traitement mensuel brut du recourant. Ils ont précisé que cette indemnité serait allouée sans intérêts moratoires en l'absence de conclusion sur ce point (art. 69 al. 1 LPA).
10.2.
10.2.1. Le recourant reproche à l'autorité cantonale d'avoir fait une application arbitraire de l'art. 31 al. 3 et 4 LPAC en fixant l'indemnité à quatre mois de son dernier traitement mensuel brut.
10.2.2. Lorsque la partie recourante se plaint de la fixation par l'autorité cantonale, dans le cadre de la fourchette prévue par la loi, du montant d'une indemnité relevant du droit cantonal, elle ne peut le faire qu'en invoquant une violation du droit fédéral (cf. consid. 2.2 supra), soit en pratique essentiellement de l'interdiction de l'arbitraire (<ref-ruling> consid. 2 p. 72; <ref-ruling> consid. 3 in fine p. 49 s.; <ref-ruling> consid. 1b in fine p. 363; arrêt 8C_37/2020 du 7 septembre 2020 consid. 5.1). Dans ce cadre, le Tribunal fédéral peut examiner si, au regard des circonstances de l'espèce, l'autorité est tombée dans l'arbitraire en abusant de son pouvoir d'appréciation (arrêt 8C_37/2020 précité consid. 5.1 et les références).
10.2.3. En l'espèce, le recourant ne démontre pas que les juges cantonaux auraient abusé de leur pouvoir d'appréciation en fixant l'indemnité à quatre mois de son traitement brut. En premier lieu, le recourant ne démontre pas l'existence d'une pratique constante de la Chambre administrative sur la question de savoir si, depuis la modification de l'art. 31 LPAC entrée en vigueur le 19 décembre 2015, l'absence ou l'existence de motifs fondés au licenciement peut constituer un élément à prendre en compte dans la fixation de l'indemnité (cf., dans un sens négatif: arrêt ATA/1195/2017 du 22 août 2017 consid. 16c; dans un sens affirmatif: arrêt ATA/1782/2019 du 10 décembre 2019 consid. 15e), de sorte qu'on ne saurait taxer d'arbitraire la prise en compte de cet élément. La quotité de l'indemnité fixée par la cour cantonale apparaît par ailleurs dans la fourchette des cas comparables tranchés par la Chambre administrative (cf. arrêts ATA/1782/2019 du 10 décembre 2019 consid. 15e; ATA/1579/2019 du 29 octobre 2019 consid. 14e). Quant aux circonstances supplémentaires que le recourant reproche à l'autorité cantonale de ne pas avoir prises en considération, elles sont soit dénuées de pertinence dans ce contexte (comme sa promotion le 28 février 2014 au rang de chef de secteur), soit non établies (comme sa situation personnelle, une violation de son droit d'être entendu prétendument reconnue implicitement par la cour cantonale ou encore un prétendu mobbing par isolement).
10.3.
10.3.1. Le recourant reproche enfin à l'autorité cantonale d'avoir violé arbitrairement l'art. 69 al. 1 LPA en considérant qu'en l'absence de conclusion sur ce point, l'indemnité qui lui était due en application de l'art. 31 al. 4 LPAC était dépourvue d'intérêts moratoires.
10.3.2. Toutefois, la Chambre administrative déduit de manière constante de l'art. 69 al. 1 LPA - aux termes duquel la juridiction administrative chargée de statuer est liée par les conclusions des parties - qu'en l'absence de conclusion sur ce point, l'indemnité allouée en application de l'art. 31 al. 4 LPAC l'est sans intérêts moratoires (arrêts ATA/1782/2019 du 10 décembre 2019 consid. 15e; ATA/1195/2017 du 22 août 2017 consid. 16d; ATA/273/2015 du 17 mars 2015 consid. 17c; ATA/193/2014 du 1er avril 2014 consid. 17). Le recourant ne prétendant pas avoir pris des conclusions tendant à l'octroi d'intérêts moratoires, son grief se révèle mal fondé.
11.
Il résulte de ce qui précède que le recours, entièrement mal fondé, doit être rejeté. Vu l'issue du litige, les frais judiciaires seront mis à la charge du recourant (<ref-law>). Bien qu'ils obtiennent gain de cause, les intimés n'ont pas droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 3000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre administrative.
Lucerne, le 15 octobre 2020
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président : Maillard
La Greffière : Elmiger-Necipoglu