Faits :
A.
A.a. A._ a été nommé en qualité de préposé à l'Office B._ du district de U._ par le Conseil d'Etat du canton du Valais. A la suite de la liquidation d'une succession dont il avait été chargé, le prénommé a fait l'objet d'une procédure pénale ainsi que d'une procédure disciplinaire ouverte par l'autorité de nomination. Le 20 juin 2012, le Conseil d'Etat a décidé de diminuer de moitié le traitement de l'intéressé pour une période de trois mois à compter du 1er juillet 2012. A._ a été acquitté par la Cour des affaires pénales du Tribunal pénal fédéral par jugement du 29 janvier 2013, confirmé par le Tribunal fédéral par arrêt du 22 juillet 2013 (arrêt 6B_235/ 2013).
Le recours formé par A._ contre la décision du gouvernement cantonal du 20 juin 2012 a été rejeté par le Tribunal cantonal du Valais (jugement du 24 mai 2013). Saisi d'un recours du prénommé, le Tribunal fédéral a annulé le jugement cantonal ainsi que la décision du Conseil d'Etat du 20 juin 2012. Il a condamné le canton du Valais à verser une indemnité de dépens au recourant et a renvoyé la cause à la juridiction précédente pour qu'elle statue à nouveau sur la répartition des frais et dépens de la procédure cantonale (arrêt 8D_3/2013 du 22 juillet 2014, publié aux <ref-ruling>).
A.b. Par jugement du 22 août 2014, le Tribunal cantonal du Valais a notamment alloué à A._ une indemnité de dépens de 2'200 fr. à la charge du canton.
A.c. Par décision du 21 janvier 2015, le Conseil d'Etat a constaté que l'arrêt du Tribunal fédéral du 22 juillet 2014 (<ref-ruling>, ci-dessus mentionné) avait éteint la procédure disciplinaire ouverte à l'encontre de A._, et il a statué sur le traitement auquel celui-ci avait droit depuis le 1er janvier 2010.
B.
B.a. Par acte du 25 février 2015, A._ a recouru devant le Tribunal cantonal du Valais en concluant à l'annulation de la décision du 21 janvier 2015 et au renvoi de la cause au Conseil d'Etat. Il faisait valoir que depuis le 25 août 2014, il avait eu des discussions avec les services de la conseillère d'Etat, et cette dernière en personne, au sujet notamment des frais d'avocat qu'il avait encourus dans les procédures engagées à son endroit.
Préalablement, le 20 février 2015, A._ avait saisi la conseillère d'Etat d'une requête tendant en particulier à ce que le gouvernement cantonal lui accorde une indemnisation pour ces frais. Au vu de la réponse (du 2 mars 2015) de celle-ci selon laquelle sa requête faisait l'objet d'un examen et le Conseil d'Etat statuerait sur les frais d'avocat en cause, l'intéressé a proposé la suspension de la procédure. Consulté par le Tribunal cantonal, le Conseil d'Etat a indiqué, le 13 juillet 2015, qu'il entendait laisser la cour cantonale trancher la question des frais d'avocat. Dans sa détermination du 18 novembre 2015 sur le recours de A._, le gouvernement cantonal a précisé que sa décision du 21 janvier 2015 comportait la renonciation à attribuer à l'intéressé une indemnité pour ses frais de défense.
Par jugement du 18 décembre 2015, la cour cantonale a rejeté le recours.
B.b. Statuant le 17 août 2016, la Ire Cour de droit social du Tribunal fédéral a déclaré irrecevable le recours constitutionnel subsidiaire interjeté par A._, mais admis son recours en matière de droit public. Elle a annulé l'arrêt cantonal du 18 décembre 2015 et renvoyé la cause à la cour cantonale pour qu'elle rende une nouvelle décision au sens des considérants (arrêt 8C_109/2016).
Statuant à nouveau le 20 octobre 2016, le Tribunal cantonal du Valais a derechef rejeté le recours de A._.
C.
A._ interjette un recours en matière de droit public. Sous suite de frais et dépens, il conclut à la réforme (ou à l'annulation) du jugement cantonal en ce sens que la décision du Conseil d'Etat du 21 janvier 2015 est annulée et le dossier renvoyé à ce dernier pour qu'il statue sur sa demande d'indemnisation.
Le Conseil d'Etat a renoncé à présenter une réponse, tout en concluant au rejet du recours.

Considérant en droit :
1.
1.1. La présente procédure a le même objet que celle qui a donné lieu à l'arrêt fédéral du 17 août 2016 8C_109/2016, à savoir la prétention du recourant au remboursement des frais d'avocat qu'il a supportés dans le cadre des procédures administrative et pénale dont le sort a justifié le réajustement de son traitement de fonctionnaire. Les conditions de recevabilité d'un recours portant sur une telle prétention ont été examinées - et admises - à l'occasion de ce précédent arrêt, auquel on peut renvoyer sur ce point (voir le consid. 1 dudit arrêt).
1.2. Pour le surplus, le recours en matière de droit public a été inter-jeté en temps utile contre une décision finale prise par un tribunal cantonal, de sorte qu'il respecte les exigences des art. 86 al. 1 let. d, 90 et 100 al. 1 LTF. Il est par conséquent recevable.
2.
2.1. Il convient de rappeler brièvement les motifs qui ont présidé à l'annulation de la précédente décision cantonale (du 18 décembre 2015). La Cour de céans a jugé qu'elle ne satisfaisait pas aux exigences de l'<ref-law> parce qu'elle ne contenait pas les motifs permettant de comprendre pourquoi la cour cantonale avait tranché dans le sens retenu. En particulier, il n'était pas possible, à la lecture de cette décision, de savoir si la cour cantonale retenait que le Conseil d'Etat avait statué de manière implicite sur la prétention du recourant et, le cas échéant, les motifs pour lesquels cette décision serait fondée, ou si, au contraire, les premiers juges avaient eux-mêmes statué sur le point querellé. En outre, l'on ne parvenait pas non plus à connaître les raisons pour lesquelles la juridiction précédente avait écarté le grief de déni de justice formel soulevé par le recourant.
2.2. A la suite de cet arrêt fédéral, la cour cantonale a rendu un nouveau jugement dans lequel elle a considéré que le recourant s'était plaint à juste titre de deux violations de procédure commises par le Conseil d'Etat. D'une part, ce dernier n'avait pas transmis à A._ les déterminations des 28 octobre 2014 et 13 janvier 2015 élaborées par le chef du Service C._ sur un projet de décision portant sur la question de l'indemnisation des frais d'avocat demandés par le prénommé, ni ne lui avait donné l'occasion de présenter des observations sur ces déterminations. Ce faisant, le Conseil d'Etat avait violé le droit d'être entendu du recourant garanti par l'art. 29 al. 2 Cst. D'autre part, la décision rendue le 21 janvier 2015 par cette autorité constatait la fin de la procédure disciplinaire ouverte contre l'intéressé et réglait la question du traitement de celui-ci, mais restait muette sur la prise en charge de ses frais d'avocat. Cette omission constituait un déni de justice (art. 29 al. 1 Cst.). Se référant à la jurisprudence (<ref-ruling> consid. 2.3.2 p. 197 s.), la cour cantonale a toutefois jugé qu'une réparation des deux vices devant elle était possible, même s'il s'agissait de violations graves, dans la mesure où son pouvoir d'examen sur le point matériel à examiner était suffisamment étendu pour garantir les intérêts légitimes du recourant ainsi qu'une correcte application de la loi, et que de surcroît l'annulation de la décision attaquée assortie du renvoi de la cause au Conseil d'Etat ne constituerait, en l'espèce, qu'une vaine formalité et aboutirait à un allongement inutile de la procédure. En effet, l'autorité inférieure s'était déterminée sur le recours de A._ et avait déposé son dossier complet, y compris les deux avis du Service C._. Le recourant avait pu en prendre connaissance et répliquer. Par ailleurs, dans sa détermination, le Conseil d'Etat avait clairement exposé sa position quant aux motifs pour lesquels il refusait de prendre en charge les frais d'avocat dont A._ demandait le remboursement. Cette détermination équivalait au contenu de la décision que l'autorité aurait dû rendre et palliait ainsi au déni de justice et à la violation de l'obligation de motiver. Partant, la cour cantonale a tranché le litige au fond. Elle a rejeté le recours de A._. Toutefois, en considération du fait qu'il avait dû recourir pour faire constater les irrégularités ayant entaché la procédure administrative, elle lui a accordé une indemnité de dépens réduite et mis la moitié seulement des frais judiciaires à sa charge.
2.3. Le recourant soutient que l'autorité judiciaire qui constate un déni de justice formel (art. 29 al. 1 Cst.) doit nécessairement renvoyer la cause à l'autorité inférieure. Selon lui, une réparation de ce vice par l'instance de recours est exclue - contrairement à ce qui est le cas en présence de certaines violations du droit d'être entendu (art. 29 al. 2 Cst.) - pour deux raisons. Premièrement, une telle réparation consacrerait "un biais de compétence" en ce sens que la décision (après réparation) n'émanerait pas de l'autorité compétente à teneur de la loi mais d'une autre autorité ou juridiction normalement et légalement incompétente. Deuxièmement, cela le privait d'un degré de juridiction.
3.
3.1. Les garanties de procédure découlant de l'art. 29 Cst. sont des droits de nature formelle dont bénéficient les parties indépendamment des chances de succès d'un recours sur le fond. Les conséquences juridiques d'une violation de ces garanties procédurales dépendent de l'étendue et de la gravité de l'atteinte en cause. Elle entraîne en principe l'annulation de la décision attaquée sous réserve de la possibilité d'une réparation du vice par l'autorité de recours (voir BERNHARD WALDMANN, in: Bundesverfassung, Waldmann/Belser/Epiney [éd.], 2015, n° 7 ad art. 29 Cst. et les références). Il n'y a donc pas règle absolue en la matière contrairement à ce que prétend le recourant.
3.2. En l'occurrence, le déni de justice commis par le Conseil d'Etat n'a porté que sur un point accessoire de la procédure en matière de rapports de droit public. Le recourant ne conteste pas qu'à la suite de son recours contre la décision du 21 janvier 2015, il a pu savoir quelle était la position de l'autorité intimée sur sa prétention. A juste titre, il ne prétend pas que celle-ci aurait adopté une autre position juridique si l'affaire lui avait été renvoyée pour rendre une décision administrative formelle, ni ne remet en cause la compétence de la Cour de droit public du Tribunal cantonal du Valais pour connaître de la question litigieuse comme autorité de recours cantonale. Enfin, force est de constater que le recourant a pu se déterminer et faire valoir tous ses moyens quant au bien-fondé de sa requête avant que la cour cantonale ne rende son arrêt. Cette dernière n'a donc pas statué à la place du Conseil d'Etat dont l'opinion était connue et on doit admettre que le recourant a eu droit à une procédure équitable devant une juridiction compétente disposant d'un plein pouvoir d'examen en fait et en droit. Par conséquent, on ne voit pas en quoi - et le recourant ne le démontre pas non plus par une motivation satisfaisant aux exigences de l'<ref-law> - la cour cantonale n'aurait pas respecté les garanties découlant de l'art. 29 al. 1 Cst. en retenant que le vice constaté pouvait être réparé devant elle, un renvoi à l'autorité de décision constituant en l'espèce une vaine formalité. Le fait que le recourant se contente, devant la Cour de céans, de se plaindre derechef d'un déni de justice sans émettre de critique contre la solution retenue par les juges cantonaux, ni quant au fond ni quant à la répartition des frais et dépens, montre que l'invocation du grief est devenu une fin en soi et qu'il ne repose sur aucun intérêt digne de protection.
Pour le reste, le recourant reconnaît que la violation de son droit d'être entendu (art. 29 al. 2 Cst.) a été réparée en procédure cantonale.
Au vu de ce qui précède, le recours doit être rejeté dans la mesure où il est recevable.
4.
Le recourant, qui succombe, supportera les frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
Les frais de justice, arrêtés à 1'500 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton du Valais, Cour de droit public.
Lucerne, le 24 octobre 2017
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président : Maillard
La Greffière : von Zwehl