Faits :
A.
B.B._ et A.B._ sont propriétaires de la parcelle n° ddd de la Commune de C._; elle jouxte au sud-est le bien-fonds n° eee, propriété de F.G._ et G.G._.
Le 11 octobre 2010, F.G._ et G.G._ ont obtenu l'autorisation de construire un mur de soutènement remplaçant un mur existant sur leur parcelle. Ce projet n'a suscité aucune opposition au cours de l'enquête publique.
Le 11 mai 2011, A.B._, agissant également pour le compte de son épouse, a sollicité du Conseil communal qu'il procède à l'examen de la conformité de ce nouvel ouvrage, voire prononce sa démolition, celui-ci étant, selon lui, trop proche de la limite autorisée. Les 30 mai et 6 juin 2011, le Conseil communal a rejeté cette requête au motif que l'autorisation de construire était en force et ne pouvait plus être révoquée; l'autorité s'est également fondée sur la garantie de la situation acquise, le mur litigieux remplaçant un ouvrage antérieur similaire.
Le 13 janvier 2016, le Conseil d'Etat du canton du Valais a déclaré irrecevable la plainte formée le 6 juillet 2011 par B.B._ et A.B._ contre la Commune de C._. Le Conseil d'Etat a estimé que les plaignants se trouvaient privés du droit de porter plainte dès lors qu'ils avaient négligé d'utiliser les moyens juridictionnels à leur disposition pour défendre leurs intérêts, en particulier la voie de l'opposition. Le Conseil d'Etat les a enfin condamnés à un émolument judiciaire de 493 fr. ainsi qu'à un montant de 7 fr. perçu pour la promotion de la santé et la prévention de maladies en application du droit cantonal.
B.
Par acte du 18 février 2016, B.B._ et A.B._ ont recouru contre cette décision à la Cour de droit public du Tribunal cantonal du Valais. Dans ce cadre, les prénommés ont en particulier soutenu que l'art. 153 al. 2 de la loi sur les communes du 5 février 2014 (LCo; RS/VS 175.1) interdisait au Conseil d'Etat de rendre une décision, seule une réponse à leur plainte étant autorisée par ce texte. Le droit cantonal ne prévoyant par ailleurs pas de frais pour le prononcé d'une telle réponse, le Conseil d'Etat n'était pas, selon les intéressés, légitimé à mettre à leur charge un émolument global de 500 fr.
La cour cantonale a rejeté le recours par arrêt du 12 août 2016. Cette dernière a considéré que le prononcé d'irrecevabilité du Conseil d'Etat du 13 janvier 2016 ne constituait pas une décision au sens du droit cantonal; elle a néanmoins jugé qu'un émolument pouvait être mis à la charge de B.B._ et A.B._, par le biais des dispositions en matière de police des constructions, ces dernières s'appliquant en tant que législation spéciale au détriment de la loi sur les communes.
C.
Agissant par la voie du recours en matière de droit public et celle du recours constitutionnel subsidiaire, B.B._ et A.B._ demandent principalement au Tribunal fédéral de réformer l'arrêt attaqué en ce sens que la décision du Conseil d'Etat du 13 janvier 2016 est annulée; subsidiairement, ils concluent au renvoi de la cause à l'instance précédente pour nouvelle décision dans le sens des considérants.
Le Tribunal cantonal ainsi que le Conseil d'Etat ont renoncé à se déterminer.

Considérant en droit :
1.
L'arrêt attaqué est une décision finale (<ref-law>) prise en dernière instance cantonale (art. 86 al. 1 let. d LTF) dans une cause de droit public (<ref-law>). Les recourants ont pris part à la procédure de recours devant l'instance précédente (<ref-law>). Les recourants sont particulièrement touchés par l'arrêt attaqué, qui confirme la décision sur les frais rendue par le Conseil d'Etat le 13 janvier 2016, mettant à leur charge un émolument judiciaire qu'ils estiment contraire à la législation cantonale (cf. arrêt 1P.385/1997 du 31 octobre 1997 consid. 2 b in fine); ils ont dès lors qualité pour agir au sens de l'<ref-law>. Les autres conditions de recevabilité étant par ailleurs réunies, la voie du recours en matière de droit public est ouverte, ce qui entraîne l'irrecevabilité du recours constitutionnel subsidiaire (<ref-law>).
2.
A titre de mesure d'instruction, les recourants demandent l'édition du dossier du Tribunal cantonal. Leur requête est satisfaite, l'instance précédente ayant déposé le dossier cantonal complet dans le délai imparti à cet effet (<ref-law>).
3.
En début de mémoire, les recourants présentent leurs propres version et appréciation des faits. Une telle argumentation, dans la mesure où elle s'écarte des faits constatés dans l'arrêt attaqué ou les complète, sans qu'il soit indiqué que ceux-ci seraient manifestement inexacts ou arbitraires, est irrecevable, le Tribunal fédéral n'étant pas une instance d'appel (<ref-ruling> consid. 3 p. 104 s.; <ref-ruling> consid. 5.2.2 p. 322).
4.
Sur le fond, les recourants se plaignent essentiellement d'une application arbitraire de l'art. 153 LCo. Selon eux, cette disposition interdisait au Conseil d'Etat d'assortir son prononcé d'irrecevabilité d'une décision les condamnant au paiement d'un émolument. Dans ce cadre, ils invoquent également une violation de la loi sur les constructions du 8 février 1996 (LC; RS/VS 705.1) et de son ordonnance d'exécution du 2 octobre 1996 (OC; RS/VS 705.100), en particulier de l'art. 63 al. 3 OC; ils reprochent également à l'instance précédente de s'être livrée à une interprétation arbitraire de l'art. 88 al. 1 de la loi sur la procédure et la juridiction administratives du 6 octobre 1976 (LPJA; RS/VS 172.6). Les recourants se prévalent enfin de l'art. 5 de la loi du 11 février 2009 fixant le tarif des frais et dépens devant les autorités judiciaires ou administratives (LTar; RS/VS 173.8); leur mémoire est toutefois exempt d'explication sur l'application de cette norme, de sorte que cet aspect du grief peut d'emblée être déclaré irrecevable (<ref-law>).
4.1. Sauf dans les cas cités expressément à l'<ref-law>, le recours ne peut pas être formé pour violation du droit cantonal en tant que tel. En revanche, il est toujours possible de faire valoir que la mauvaise application du droit cantonal constitue une violation du droit fédéral, en particulier qu'elle est arbitraire au sens de l'art. 9 Cst. ou contraire à d'autres motifs de droit constitutionnel (<ref-ruling> consid. 1.2 p. 145).
Appelé à revoir l'interprétation d'une norme cantonale sous l'angle restreint 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. 2.4 p. 5; <ref-ruling> consid. 4.2 p. 560).
4.2. D'après l'art. 144 al. 1 LCo, dont le titre marginal est "Principe général de surveillance", les collectivités de droit public sont placées sous la surveillance du Conseil d'Etat qui veille à ce qu'elles se régissent et s'administrent conformément à la Constitution et aux lois. En sa qualité d'autorité de surveillance, le Conseil d'Etat est habilité à recevoir les plaintes de toute personne intéressée dirigées contre une administration ou un organe d'une collectivité de droit public (cf. art. 153 al. 1 1ère phrase LCo). La personne agissant par cette voie a droit à une réponse de l'autorité de surveillance (art. 153 al. 2 LCo).
L'arrêt attaqué rappelle par ailleurs qu'en droit valaisan la police des constructions est régie par les art. 49 ss LC ainsi que par l'ordonnance sur les constructions (OC). Aux termes de l'art. 60 al. 1 OC, si les autorités compétentes en matière de police des constructions négligent leurs tâches ou ne sont pas en mesure de les remplir et que des intérêts publics sont de ce fait menacés, le Conseil d'Etat, en qualité d'autorité de surveillance de la procédure d'autorisation de construire et de la police des constructions, doit se substituer à elles et ordonner les mesures nécessaires. Dans ce cas, le Conseil d'Etat impartit aux autorités défaillantes un délai convenable pour l'exécution de leurs tâches (al. 2).
4.3. En l'espèce et à titre préalable, la cour cantonale a admis que le prononcé d'irrecevabilité du Conseil d'Etat du 13 janvier 2016, se limitant à un refus d'entrer en matière sur une plainte, en raison de son caractère subsidiaire, ne constituait pas une décision au sens du droit cantonal, en particulier de l'art. 5 LPJA. Le Tribunal cantonal a ensuite rappelé que le recours cantonal de droit administratif n'était, dans la règle, ouvert qu'à l'encontre d'une décision (cf. art. 72 LPJA). La cour cantonale a de surcroît précisé qu'un pourvoi ne portant que sur le sort des frais était en principe exclu dans une cause dont elle ne pouvait connaître du fond (cf. art. 77 let. b LPJA); l'instance précédente a néanmoins renoncé à l'examen des exceptions apportées à cette exclusion par l'art. 77bis LPJA, jugeant le recours en tout état mal fondé.
Entrant en matière sur le recours, le Tribunal cantonal a considéré que la surveillance instaurée par la loi sur les constructions constituait une compétence spéciale ayant le pas sur le régime ordinaire de surveillance des art. 144 et 153 LCo. La cour cantonale en a déduit que les règles en matière d'émoluments prévues par la législation sur les constructions s'appliquaient également aux plaintes formulées dans ce cadre auprès de l'autorité de surveillance. A ce sujet, elle a précisé que les frais relatifs à la police des constructions étaient régis par la LPJA (art. 63 al. 3 OC fondé sur l'art. 34 al. 2 let. c LC), en particulier par les art. 88 ss LPJA. Selon l'art. 88 al. 1 LPJA, celui qui provoque ou requiert une démarche de l'administration acquitte l'émolument fixé par l'autorité; il peut être tenu de rembourser tout ou partie des débours. Considérant que cette disposition prévoyait un régime général, le Tribunal cantonal a jugé que celle-ci permettait non seulement la perception d'un émolument dans l'hypothèse d'une décision, mais également en cas de refus d'entrer en matière sur une dénonciation dans des affaires de surveillance. La cour cantonale a enfin estimé que cette approche n'était pas non plus contraire à la LTar, cette loi prévoyant à son art. 1er al. 2 let. d un renvoi à la LPJA en matière de frais et dépens dans les causes administratives.
4.4. Les recourants ne contestent pas que les compétences de surveillance dont jouit le Conseil d'Etat en matière de police des constructions trouvent leur fondement dans la législation cantonale sur les constructions. Ils soutiennent en revanche que ni la loi sur les constructions ni son ordonnance d'exécution ne contiendraient de dispositions régissant le dépôt, le traitement et les suites à réserver à une plainte. Selon eux, la législation cantonale sur les constructions ne saurait dès lors s'appliquer aux dépens de l'art. 153 LCo, consacrant expressément le droit de porter plainte. Pour peu qu'on comprenne les recourants sur ce point, l'application de l'art. 153 LCo n'autoriserait pas l'autorité à rendre une décision au sens de l'art. 5 LPJA, spécialement une décision portant sur les frais, mais uniquement une réponse. Ils estiment qu'en tout état de cause le régime des frais relatifs à la police des constructions réglé par les art. 63 al. 3 OC et 88 al. 1 LPJA ne saurait s'appliquer à une plainte déposée conformément à l'art. 153 LCo. A les suivre, les frais de l'art. 63 al. 3 OC ne couvriraient que les démarches effectuées dans un "cas de non-conformité au droit des constructions" à l'instar des inspections locales ou encore de la tenue d'auditions; ces frais concerneraient également les démarches liées à une procédure de remise en état au sens de l'art. 51 LC. Les recourants en déduisent en définitive que seules les parties à une procédure du droit des constructions pourraient être condamnées à ces frais, qualité qu'ils ne revêtiraient pas en tant que plaignants.
4.5. Il faut accorder aux recourants que ni la loi sur les constructions ni son ordonnance d'exécution ne prévoient explicitement le droit de déposer une plainte à l'autorité de surveillance. On ne saurait toutefois en déduire - contrairement à ce qu'affirment les recourants - qu'une telle démarche serait nécessairement exclue du domaine, respectivement de la notion de police des constructions, en particulier lorsque, comme en l'espèce, la dénonciation a pour objet le refus d'une autorité communale de constater le caractère prétendument irrégulier d'un ouvrage. Cette compétence relève en effet indéniablement de ce domaine du droit (cf. art. 49 ss LC), de sorte que l'on ne voit pas en quoi il serait arbitraire d'avoir jugé que la plainte des recourants tombait sous le coup de la loi sur les constructions - en tant que lex specialis -, singulièrement sous le coup des dispositions réglant le sort des frais en la matière. Il faut à cet égard, avec la cour cantonale, reconnaître qu'à rigueur de texte ni l'art. 63 al. 3 OC ni l'art. 34 al. 2 let. c LC, sur lequel se fonde l'ordonnance, n'interdisent qu'une plainte soit assortie de frais ni ne réservent ces derniers aux seules décisions, comme le soutiennent implicitement les recourants; il en va d'ailleurs de même de l'art. 88 al. 1 LPJA qui prévoit, de façon générale, la perception de débours pour toute démarche de l'autorité provoquée ou requise par un administré. On ne saurait en outre réserver un écho favorable aux allégations des recourants lorsqu'ils prétendent n'avoir sollicité aucune intervention de l'autorité, mais procédé dans l'intérêt de la collectivité par le "dépôt citoyen" d'une dénonciation: il est douteux qu'en saisissant le Conseil d'Etat d'une plainte, dans le but de remettre en cause une construction directement voisine de leur parcelle, les recourants aient agi de manière totalement désintéressée; ces derniers ont d'ailleurs, contrairement à ce qu'ils affirment, interpellé le Conseil d'Etat afin de s'enquérir de l'avancement du dossier et des démarches envisagées dans le traitement de leur dénonciation (cf. courrier du 9 janvier 2013). Dans ces conditions, il n'apparaît pas critiquable d'avoir considéré que les recourants ont requis l'intervention de l'autorité de surveillance, au sens de l'art. 88 al. 1 LPJA, et de leur faire en conséquence supporter les frais et débours engendrés par le dépôt de leur plainte.
4.6. En conclusion, la solution du Tribunal cantonal repose sur une interprétation soutenable des dispositions cantonales et aboutit à un résultat exempt d'arbitraire. Entièrement mal fondé, le grief doit être écarté pour autant que recevable.
5.
Les considérants qui précèdent conduisent au rejet du recours, dans la mesure de sa recevabilité, aux frais des recourants, qui succombent (art. 65 et 66 al. 1 et 5 LTF). Il n'est pas alloué de dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours constitutionnel subsidiaire est irrecevable.
2.
Le recours en matière de droit public est rejeté dans la mesure où il est recevable.
3.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge solidaire des recourants.
4.
Le présent arrêt est communiqué au mandataire des recourants, à la Commune de C._, au Conseil d'Etat du canton du Valais ainsi qu'au Tribunal cantonal du canton du Valais, Cour de droit public.
Lausanne, le 14 décembre 2016
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Fonjallaz
Le Greffier : Alvarez