Faits :
A.
A._, ressortissant italien né en 1960, célibataire et sans enfant, est entré en Suisse en 1969. Il est au bénéfice d'une autorisation d'établissement UE/AELE. Durant son séjour dans ce pays, il a connu une faillite en 1993, occupé de façon irrégulière quelques emplois et bénéficié de l'aide sociale durant plusieurs années. Il exerce une activité indépendante de carrossier depuis le 1 er juin 2012.
Par jugement du 7 novembre 2013, il a été reconnu coupable d'actes d'ordre sexuel avec des enfants, contrainte sexuelle, viol et actes de pornographie, commis sur une période allant de novembre 2008 à fin mars 2011, au préjudice de la fille de sa compagne, née en 1995 et souffrant d'un léger retard mental. La peine de trois ans et demi initialement prononcée par le tribunal de première instance a été augmentée, sur recours du ministère public, à quatre ans et demi de peine privative de liberté. L'intéressé a en outre été soumis à un traitement psychothérapeutique ambulatoire en milieu carcéral. Il exécute sa peine depuis le 28 janvier 2016.
B.
Par décision du 9 avril 2018, le Service des migrations de la République et canton de Neuchâtel (ci-après: le Service des migrations) a révoqué l'autorisation d'établissement UE/AELE de A._. Le Département de l'économie et de l'action sociale de la République et canton de Neuchâtel (ci-après: le Département) a confirmé cette décision le 15 octobre 2018. A._ a contesté ce prononcé auprès de la Cour de droit public du Tribunal cantonal de la République et canton de Neuchâtel (ci-après: le Tribunal cantonal) qui, par arrêt du 29 mars 2019, a admis le recours et lui a adressé un avertissement formel.
C.
Agissant par la voie du recours en matière de droit public, le Secrétariat d'Etat aux migrations (ci-après: le Secrétariat d'Etat) demande au Tribunal fédéral d'annuler l'arrêt du Tribunal cantonal du 29 mars 2019 et de confirmer la décision du Département du 15 octobre 2018 prononçant la révocation de l'autorisation d'établissement UE/AELE de A._.
A._ et le Tribunal cantonal concluent tous deux au rejet du recours, alors que le Service des migrations conclut à son admission.

Considérant en droit :
1.
1.1. En vertu de l'art. 14 al. 2 de l'ordonnance du 17 novembre 1999 sur l'organisation du Département fédéral de justice et police (Org DFJP; RS 172.213.1), le Secrétariat d'Etat a qualité pour recourir devant le Tribunal fédéral (<ref-law>), dans le domaine du droit des étrangers, contre des décisions cantonales de dernière instance. Infirmant la révocation de l'autorisation d'établissement UE/AELE de l'intimé, l'arrêt entrepris peut faire l'objet d'un recours en matière de droit public, dès lors qu'il existe potentiellement un droit, du point de vue de l'étranger intimé, au maintien de cette autorisation (<ref-ruling> consid. 1.1 p. 179) et que le Secrétariat d'Etat peut contester l'arrêt cantonal qui reconnaît l'existence d'un tel droit (cf. <ref-ruling> consid. 1.2 p. 140 s.; arrêt 2C_523/2016 du 14 novembre 2016 consid. 1.1). La présente cause ne tombe ainsi pas sous le coup de l'art. 83 let. c ch. 2 LTF, ni d'aucune autre clause d'irrecevabilité figurant à l'<ref-law>.
1.2. Au surplus, le recours est dirigé contre une décision finale (<ref-law>) rendue dans une cause de droit public (<ref-law>) par un tribunal supérieur de dernière instance cantonale (art. 86 al. 1 let. d et al. 2 LTF). Déposé dans le délai (<ref-law>) et la forme (<ref-law>) prévus par la loi, le recours est en principe recevable.
2.
Le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (<ref-law>), sous réserve des cas prévus à l'<ref-law> (<ref-ruling> consid. 4.4.3 p. 156). Le recourant ne peut critiquer les constatations de fait ressortant de la décision attaquée que si celles-ci ont été effectuées en violation du droit au sens de l'<ref-law> ou de manière manifestement inexacte, c'est-à-dire arbitraire, et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>; <ref-ruling> consid. 6 p. 358). Conformément à l'<ref-law>, le recourant doit expliquer de manière circonstanciée en quoi ces conditions seraient réalisées. Le Tribunal fédéral n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou sur l'appréciation des preuves (<ref-ruling> consid. 6.3 p. 375). Par ailleurs, aucun fait nouveau ni preuve nouvelle ne peut en principe être présenté devant le Tribunal fédéral (<ref-law>).
3.
3.1. Dans l'arrêt entrepris, le Tribunal cantonal a retenu que l'intimé avait été condamné pour des infractions très graves, car dirigées contre un bien juridique particulièrement important. Il a également mentionné que ces infractions avaient été commises sur une longue période, de plus de deux ans. Prenant en compte l'expertise psychiatrique figurant au dossier pénal et en particulier l'avis de l'expert qui a expressément reconnu qu'un risque de récidive ne pouvait pas être exclu, l'autorité précédente a également admis un tel risque dans le cadre de la présente procédure. Elle a par ailleurs considéré que celui-ci était d'autant plus important que la nouvelle amie de l'intimé était mère d'un enfant en bas âge. Sur cette base, elle a jugé que la révocation de l'autorisation d'établissement UE/AELE de l'intimé était conforme à l'<ref-law> (RS 0.142.112.681). L'autorité précédente a ensuite examiné la proportionnalité de la mesure de révocation de l'autorisation d'établissement. A ce propos, prenant en particulier en compte la peine infligée à l'intimé, la durée du séjour en Suisse de celui-ci, les faibles perspectives de retrouver un travail de carrossier indépendant en Italie, les nombreuses dettes, la présence de la famille proche et de l'amie de l'intimé en Suisse, ainsi que l'existence d'un antécédent pénal mineur, le Tribunal cantonal a considéré que la révocation de l'autorisation d'établissement était une mesure inadéquate et a prononcé un avertissement formel à la place.
3.2. Le recourant, à l'instar du Tribunal cantonal, admet l'existence d'un risque de récidive de l'intimé et, partant, d'un cas d'application de l'<ref-law>. Il conteste en revanche l'application de l'art. 96 LEI (RS 142.20, respectivement dans sa version en vigueur avant le 1 er janvier 2019 [RO 2007 5437; ci-après LEtr]; cf. art. 126 LEI) faite par l'autorité précédente. S'agissant de la proportionnalité de la mesure, il relève en bref l'extrême gravité des infractions pénales commises par l'intimé, l'existence d'une précédente condamnation pénale et le fait qu'il n'est pas impossible pour l'intimé d'exercer une activité salariée ou indépendante de carrossier dans son pays d'origine, rappelant que l'intégration de celui-ci en Suisse n'a rien d'exceptionnel. S'il prend en considération la durée de présence en Suisse de l'intimé, le recourant constate toutefois que celui-ci n'y est pas né et que l'importance à reconnaître à cette circonstance doit être grandement relativisée, compte tenu de la gravité des infractions commises.
3.3. Finalement, l'intimé conteste l'appréciation du recourant quant à la proportionnalité de la mesure de révocation de son autorisation d'établissement. Il se prévaut de sa situation extrêmement particulière de ressortissant de l'Union européenne, âgé, qui a certes commis un crime grave, mais qui a passé pratiquement toute sa vie en Suisse et qui n'a aucun lien avec son pays d'origine.
3.4. Le litige porte donc sur le point de savoir si c'est à bon droit que le Tribunal cantonal a retenu que la révocation de l'autorisation d'établissement UE/AELE de l'intimé constituait une mesure disproportionnée et, partant, annulé la décision sur recours du Département.
4.
Le Tribunal cantonal a correctement présenté le droit applicable (art. 2 al. 2 LEI, ancien art. 62 al. 1 let. b par renvoi de l'ancien art. 63 al. 2, 96 al. 1 LEtr et 5 par. 1 annexe I ALCP) et la jurisprudence topique, relative notamment à la peine privative de liberté de longue durée (<ref-ruling> consid. 2.1 p. 147) et à la notion d'ordre public (<ref-ruling> consid. 5.3 p. 125 s.), de sorte qu'il y est renvoyé.
5.
5.1. En ayant été condamné à quatre ans et demi de peine privative de liberté, l'intimé réunit les conditions de la peine privative de liberté de longue durée de l'ancien art. 62 al. 1 let. b, par renvoi de l'ancien art. 63 al. 2 LEtr, permettant la révocation de son autorisation d'établissement. L'intimé ne le conteste d'ailleurs pas.
5.2. En premier lieu, même si aucune des parties à la procédure ne remet en question l'existence d'un risque de récidive, il convient malgré tout d'examiner l'application faite de l'<ref-law> par l'autorité précédente (cf. <ref-law>). A ce propos, il ressort des faits de l'arrêt entrepris et liant le Tribunal fédéral (cf. <ref-law>) que, selon l'expert psychiatre mandaté par la justice pénale, un risque de récidive ne peut pas être exclu, mais peut être diminué par la poursuite du traitement thérapeutique entrepris. L'expert explique notamment que le risque de récidive, qui " se situe sur le terrain des moeurs et donc de la sexualité ", est susceptible de réapparaître dans un contexte de perte de repères relationnels pour autant que la potentielle victime soit dans l'entourage de l'intimé. Or, la nouvelle amie de celui-ci est justement mère d'un enfant en bas âge. Dans ces conditions, et en prenant également en compte une précédente condamnation (certes de moindre importance) intervenue en 2003, c'est à juste titre que le Tribunal cantonal a admis l'existence d'un risque de récidive.
5.3. Reste en définitive à examiner si la mesure de révocation de l'autorisation d'établissement confirmée par le Département et infirmée, sur recours, par le Tribunal cantonal, respecte le principe de proportionnalité prévu par l'ancien art. 96 al. 1 LEtr.
5.3.1. De jurisprudence constante, la question de la proportionnalité d'une révocation d'autorisation doit être tranchée au regard de toutes les circonstances du cas d'espèce, les critères déterminants se rapportant notamment en cas de condamnation pénale à la gravité de l'infraction, à la culpabilité de l'auteur, au temps écoulé depuis l'infraction, au comportement de celui-ci pendant cette période, au degré de son intégration et à la durée de son séjour antérieur, ainsi qu'aux inconvénients qui le menacent, lui et sa famille, en cas de révocation (cf. <ref-ruling> consid. 2.3.3 p. 34 ss; <ref-ruling> consid. 4.3 p. 381 s.). Lorsque la mesure de révocation est prononcée en raison de la commission d'une infraction, la peine infligée par le juge pénal est le premier critère à utiliser pour évaluer la gravité de la faute et pour procéder à la pesée des intérêts (cf. <ref-ruling> consid. 2.2.1 p. 19 et les références; arrêt 2C_970/2017 du 7 mars 2018 consid. 4.1). La durée de séjour en Suisse d'un étranger constitue un autre critère très important. Plus cette durée est longue, plus les conditions pour prononcer l'expulsion administrative doivent être appréciées restrictivement (cf. arrêt 2C_970/2017 du 7 mars 2018 consid. 4.1). La révocation de l'autorisation d'établissement d'un étranger qui séjourne depuis sa petite enfance en Suisse doit se faire avec une retenue particulière, mais n'est pas exclue en cas d'infractions très graves, en particulier en cas de violence, de délits sexuels, de graves infractions à la loi fédérale sur les stupéfiants, ou en cas de récidive, même dans le cas d'un étranger né en Suisse et qui y a passé l'entier de sa vie (cf. arrêts 2C_308/2017 du 21 février 2018 consid. 4.3 et les références). On tiendra alors particulièrement compte de l'intensité des liens de l'étranger avec la Suisse et des difficultés de réintégration dans son pays d'origine (arrêts 2C_970/2017 du 7 mars 2018 consid. 4.1 et les références).
5.3.2. En premier lieu, on doit constater que l'intimé, qui est arrivé en Suisse il y a environ 50 ans, est célibataire et n'a pas d'enfant. En outre, il est important de rappeler que, durant son séjour, il a été condamné à quatre ans et demi de peine privative de liberté pour actes d'ordre sexuel avec des enfants, contrainte sexuelle, viol et actes de pornographie, le tout sur une période de plus de deux ans, au préjudice de la fille de sa compagne. Dans la mesure où le bien juridique menacé est important, le Tribunal fédéral se montre particulièrement rigoureux dans l'analyse de la proportionnalité (cf. arrêt 2C_95/2018 du 7 août 2018 consid. 5.2 et les références). L'intérêt public à l'éloignement de l'intimé est ainsi extrêmement élevé.
Certes, l'intimé peut faire valoir un intérêt privé à rester en Suisse, intérêt que le Tribunal cantonal a considéré comme étant supérieur à l'intérêt public précité. Cette autorité ne saurait cependant être suivie. En effet, l'autorité précédente a essentiellement pris en compte la durée du séjour en Suisse de l'intimé et l'absence de perspectives professionnelles en Italie pour ne pas confirmer la mesure de révocation qui était contestée devant lui. Or, ces éléments ne sauraient être prépondérants par rapport à l'importante condamnation et la faute extrêmement grave de l'intimé. Tout d'abord, s'il est vrai qu'il se trouve en Suisse depuis de très nombreuses années, force est de constater que l'intimé n'est pas marié, n'a pas d'enfant et ne fait pas valoir y bénéficier de liens particuliers. Si sa famille et son amie actuelle se trouvent en Suisse, rien ne permet de retenir une intégration sociale particulière. Au contraire, l'intimé a bénéficié durant plusieurs années de l'aide sociale et présente de nombreuses dettes en lien notamment avec une faillite survenue en 1993, soit il y a bientôt 30 ans. Son intégration professionnelle ne saurait dès lors être considérée comme étant particulièrement poussée, même si, depuis 2012, il exerce une activité indépendante de carrossier, activité qu'il souhaite reprendre à sa sortie de prison. Cette activité, qu'il n'a exercé que durant un peu plus de trois ans et qui génère un chiffre d'affaires mensuel variant entre 4'000 fr. et 12'000 fr., n'est néanmoins aucunement suffisante pour contrebalancer l'importance de sa condamnation et l'intérêt public existant à la révocation de son autorisation d'établissement. A cela s'ajoute que, contrairement à ce que semble penser le Tribunal cantonal, un retour en Italie ne sera pas insurmontable. Tout d'abord, l'Italie est suffisamment proche de la Suisse pour permettre à l'intimé de maintenir des contacts sociaux avec sa famille et continuer de voir son amie, que ce soit dans son pays d'origine ou lors de visite en Suisse. De plus, même si l'on ne peut nier que cela ne sera pas aisé, l'intimé bénéficie d'une formation qui lui permettra de retrouver une activité salariée ou indépendante dans son pays d'origine, malgré son âge. A tout le moins, on ne voit pas en quoi il serait plus facile de retrouver une activité en Suisse plutôt qu'en Italie, l'intimé étant depuis plusieurs années (et encore durant plusieurs mois) en détention et, par conséquent, éloigné du monde du travail. S'il affirme avoir gardé certains clients, ainsi que son local, ces simples affirmations ne sauraient suffire pour retenir un intérêt personnel à pouvoir rester en Suisse, supérieur à l'intérêt public tendant à protéger l'ordre et la sécurité publics de ce pays. Rien ne permet de considérer au demeurant que l'intimé ne pourrait pas poursuivre le traitement thérapeutique entamé en Suisse dans son pays d'origine.
5.4. Dans ces conditions, c'est à tort que l'autorité précédente a jugé que la mesure de révocation de l'autorisation d'établissement de l'intéressé était disproportionnée. En infirmant la décision sur recours du Département, l'autorité précédente a violé l'ancien art. 96 al. 1 LEtr. Il convient donc d'admettre le recours, d'annuler l'arrêt du Tribunal cantonal du 29 mars 2019 et de confirmer la décision sur recours du Département du 15 octobre 2018.
6.
Succombant, l'intimé doit supporter les frais judiciaires (<ref-law>). Il n'y a pas lieu d'allouer de dépens à l'autorité recourante (<ref-law>). La cause est renvoyée au Tribunal cantonal pour qu'il procède à une nouvelle répartition des frais et dépens de la procédure qui s'est déroulée devant lui (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, l'arrêt du 29 mars 2019 rendu par le Tribunal cantonal est annulé. La décision sur recours du 15 octobre 2018 du Département est confirmée.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge de l'intimé.
3.
La cause est renvoyée au Tribunal cantonal pour nouvelle décision sur les frais et les dépens de la procédure antérieure.
4.
Le présent arrêt est communiqué au recourant, au mandataire de l'intimé, au Service des migrations, au Département de l'économie et de l'action sociale et à la Cour de droit public du Tribunal cantonal de la République et canton de Neuchâtel.
Lausanne, le 12 septembre 2019
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Juge présidant : Zünd
Le Greffier : Tissot-Daguette