Faits:
A.
Le 30 mai 2011, le Conseil municipal de E._ a accordé des permis de construire pour douze immeubles d'habitation aux requérants "Z._". B.X._ et A.X._, ainsi que D.Y._ et C.Y._ ont recouru avec succès contre cette décision auprès du Conseil d'Etat valaisan. Celui-ci a ordonné à Z._ SA de verser une indemnité de 1'500 fr. à titre de dépens aux quatre recourants, créanciers solidaires (ch. 6 du dispositif de la décision du 24 octobre 2012).
B.
Par mémoire du 29 novembre 2012, B.X._, A.X._, D.Y._ et C.Y._ ont interjeté recours contre cette décision, requérant l'annulation du chiffre 6 de son dispositif, la fixation de l'indemnité de dépens par le Tribunal cantonal et, à titre subsidiaire, le renvoi de la cause sur cette question à l'autorité précédente. Ils ont produit la liste de frais de leur conseil, qui s'élevait pour la période de décembre 2009 à fin octobre 2012 à 7'953 fr.
Le 29 mai 2013, le Tribunal cantonal valaisan a rejeté ce recours.
C.
Par acte du 27 juin 2013, B.X._ et A.X._, ainsi que D.Y._ et C.Y._ forment recours contre cette décision, concluant à son annulation. Ils demandent que le Tribunal fédéral fixe l'indemnité de dépens et, subsidiairement, que la cause soit renvoyée au Tribunal cantonal pour nouvelle décision.
Invitée à se déterminer, Z._ SA, par le biais de son mandataire, n'a pas désiré se prononcer ou être partie dans la procédure fédérale. Elle a relevé qu'elle ignorait comment elle avait été impliquée dans cette cause, affirmant notamment n'être pas la destinataire des décisions rendues dans celle-ci. Quant au Conseil d'Etat valaisan, il a conclu au rejet du recours dans la mesure de sa recevabilité. Le Tribunal cantonal a renoncé à se déterminer. Les recourants n'ont pas déposé d'observations complémentaires.

Considérant en droit:
1.
Le Tribunal fédéral examine d'office sa compétence (<ref-law>) et contrôle librement les conditions de recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 133; <ref-ruling> consid. 1 p. 439).
1.1. L'arrêt attaqué a confirmé la décision du Conseil d'Etat valaisan statuant dans une procédure relative à des permis de construire. Il s'agit donc d'une cause de droit public (<ref-law>). Dès lors qu'une violation arbitraire du droit cantonal est invoquée à l'appui du recours au Tribunal fédéral (art. 95 let. a et 106 al. 2 LTF; <ref-ruling> consid. 1.2 p. 253; <ref-ruling> consid. 2.1 p. 3; <ref-ruling> consid. 2.4 p. 249) et qu'aucune des exceptions de l'<ref-law> n'est réalisée, le recours en matière de droit public est ouvert.
1.2. Les recourants, assistés d'un avocat, intitulent leur mémoire "recours en matière de droit public", puis examinent les conditions de recevabilité du recours constitutionnel subsidiaire.
Toutefois, l'indication erronée d'un type de recours ne nuit pas à son auteur pour autant que les conditions de recevabilité du recours qui aurait dû être interjeté soient réunies (<ref-ruling> consid. 3.3 p. 444; <ref-ruling> consid. 1.2 p. 382 et les arrêts cités ). En l'occurrence, les recourants, qui sont atteints par l'arrêt entrepris leur refusant une indemnité de dépens supérieure à celle fixée par le Conseil d'Etat, ont un intérêt digne de protection à son annulation ou à sa modification (<ref-law>). Le jugement entrepris a été rendu par une autorité statuant en dernière instance cantonale (art. 86 al. 1 let. d LTF) et doit être considéré comme une décision finale (<ref-law>), puisqu'il suit la nature de la décision sur le fond (arrêts 2C_162/2013 du 8 juillet 2013 consid. 2.1; 4A_200/2011 du 29 juin 2011 consid. 1.1). En conséquence, l'écriture des recourants - déposée en temps utile (<ref-law>) - peut être traitée comme un recours en matière de droit public et il y a lieu d'entrer en matière.
1.3. Quant à la partie intimée, elle est, selon le dispositif de la décision du Conseil d'Etat, la débitrice des dépens alloués aux recourants, qualité qu'elle n'a pas remise en cause devant l'autorité supérieure. L'intimée n'ignore pas non plus cette obligation puisque cette décision lui a été notifiée par l'intermédiaire de son conseil. Elle sait également que les recourants ont contesté le montant de l'indemnité car elle a été invitée à participer à la procédure devant l'autorité précédente, puis a reçu une copie de l'arrêt cantonal. Dès lors qu'en cas d'admission du recours, le montant mis à sa charge pourrait être augmenté, elle est concernée par l'issue du présent litige. Il se justifiait donc de lui donner l'occasion de se prononcer sur les arguments des recourants (cf. art. 29 al. 2 Cst.), étant ensuite libre de s'en remettre à justice, ainsi qu'elle l'a fait au niveau cantonal, ou de renoncer à se déterminer.
2.
Invoquant l'art. 9 Cst., les recourants reprochent à l'autorité précédente une application arbitraire de la loi cantonale du 11 février 2009 fixant le tarif des frais et dépens devant les autorités judiciaires et administratives (LTar; RS/VS 173.8). Ils soutiennent en substance qu'au vu de la liste de frais de leur mandataire, qui s'élève à près de 8'000 fr., le montant alloué de 1'500 fr. serait manifestement insuffisant. En confirmant pourtant une telle indemnité, les juges cantonaux violeraient l'art. 27 al. 1 LTar qui prévoit que les honoraires sont fixés entre un minimum et un maximum prévus par la LTar - 550 fr. et 8'800 fr. en matière de recours administratif (art. 37 al. 2 LTar) -, d'après la nature et l'importance de la cause, ses difficultés, l'ampleur du travail, le temps utilement consacré par le conseil juridique, et la situation financière de la partie.
2.1. Selon la jurisprudence, le juge n'est pas toujours tenu de motiver la décision par laquelle il fixe le montant des dépens alloués à une partie obtenant totalement ou partiellement gain de cause dans un procès; il est admis de façon générale que le juge est en mesure de se rendre compte de la nature et de l'ampleur des opérations que le procès a nécessitées. Lorsqu'il existe un tarif ou une règle légale fixant des minima et maxima, le juge ne doit motiver sa décision que s'il sort de ces limites, si des éléments extraordinaires sont invoqués par la partie concernée ou si le juge s'écarte d'une note de frais produite par l'intéressé et alloue une indemnité inférieure au montant habituel, en dépit d'une pratique bien définie (<ref-ruling> consid. 2.a p. 1; arrêt 9C_801/2012 du 28 octobre 2013 consid. 5.1 destiné à la publication).
S'agissant de l'application du droit cantonal, le Tribunal fédéral ne revoit la cause que sous l'angle de l'arbitraire. Il ne s'écarte de la solution retenue par l'autorité de dernière instance cantonale que si la décision attaquée apparaît insoutenable, en contradiction manifeste avec la situation effective, adoptée sans motifs objectifs ou en violation d'un droit certain (<ref-ruling> consid. 5.2 p. 61; <ref-ruling> consid. 7.1 p. 51). Pour qu'une décision soit annulée pour cause d'arbitraire, il ne suffit pas que sa motivation soit insoutenable; il faut encore que cette décision soit arbitraire dans son résultat (ATF <ref-ruling> consid. 7.1 p. 51 et les arrêts cités ).
2.2. En l'espèce, l'indemnité de dépens - 1'500 fr. - paraît peu élevée en comparaison du montant figurant sur la note de frais du mandataire des recourants (7'953 fr.). Cependant, le raisonnement tenu par le Tribunal cantonal pour confirmer la décision du Conseil d'Etat n'apparaît pas insoutenable.
En effet, les premiers juges ont tout d'abord constaté que le montant alloué respectait les limites posées à l'art. 37 al. 2 LTar (550 fr. et 8'800 fr.). Ils ont ensuite rappelé qu'ils n'étaient pas liés par le décompte de l'avocat, pièce dont par ailleurs le Conseil d'Etat n'avait pas eu connaissance au moment de statuer puisqu'elle n'a été produite que devant le Tribunal cantonal. Si, selon le Conseil d'Etat, la difficulté de la cause pouvait être qualifiée de "moyenne", la juridiction précédente a en revanche estimé que l'affaire était un cas classique et ordinaire en matière de construction (application du tableau de zones, relations entre le droit communal et le droit cantonal, contestation de préavis techniques, échanges d'écritures d'une dizaine de pages, correspondances usuelles et absence de séance sur les lieux ou d'autre mesure d'instruction). Cette appréciation n'a pas été remise en cause par les recourants, qui n'ont notamment pas soutenu que l'un des points susmentionnés ou une autre question aurait nécessité un travail particulièrement important dans la présente affaire. En se limitant à invoquer avoir combattu "l'un des plus gros projets immobiliers" et à renvoyer aux pièces du dossier sans autre précision, ils ne remplissent pas les exigences de motivation découlant de l'<ref-law> et de l'<ref-law> en matière de droit constitutionnel (ATF <ref-ruling>71 consid. 1.4 p. 176 et les arrêts cités). De plus, ils n'expliquent pas en quoi les critères posés à l'art. 27 LTar n'auraient pas été respectés ou auraient été ignorés au moment de l'appréciation de l'instance précédente, ni ne démontrent que le montant invoqué à titre de pratique cantonale serait erroné; ils affirment au contraire que le Tribunal cantonal "tente de cristalliser coûte que coûte une pratique [alléguée] arbitraire et choquante". Certes, il ne peut être reproché à un mandataire professionnel d'examiner une cause sous différents angles et il lui appartient, d'entente avec ses mandants, de déterminer la stratégie à suivre. Toutefois, l'absence de pertinence de certains griefs - surtout si cela devait être manifeste ainsi que cela semble ressortir de la décision du Conseil d'Etat (cf. en particulier p. 6 s. dudit acte) - peut amener l'autorité à considérer que le temps utilement consacré à ces questions pouvait être limité (cf. art 4 al. 1 et 27 al. 1 LTar; arrêt 1P.69/2003 du 16 mai 2003 consid. 2.2).
2.3. En conséquence, en confirmant l'augmentation de 500 fr. par rapport au montant de l'indemnité allouée usuellement dans ce type d'affaire (entre 800 fr. et 1'000 fr.), le Tribunal cantonal n'a pas procédé de manière arbitraire.
3.
Il s'ensuit que le recours doit être rejeté dans la mesure de sa recevabilité. Les recourants qui succombent supportent solidairement les frais judiciaires (<ref-law>). Il n'est pas alloué de dépens à l'intimée qui a renoncé à procéder (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté dans la mesure de sa recevabilité.
2.
Il n'est pas alloué de dépens.
3.
Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge des recourants, solidairement entre eux.
4.
Le présent arrêt est communiqué aux mandataires des parties, au Conseil d'Etat du canton du Valais et à la Cour de droit public du Tribunal cantonal du canton du Valais.
Lausanne, le 5 décembre 2013
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Fonjallaz
La Greffière: Kropf