Faits: A. X._, titulaire du certificat de maturité pédagogique dès 1969, du diplôme d'enseignement dès 1970 et du brevet pédagogique dès 1974, a enseigné à A._ de 1969 à 1972, puis à B._ de 1972 à 1989, en particulier au Cycle d'orientation régional de B._ (ci-après: le Cycle). Il a exercé son activité au Collège C._ dès 1990 et au Collège D._ à partir de l'année scolaire 1995/1996. Durant l'année scolaire 1997/1998, il a notamment enseigné le français dans la classe xxx, dont Y._ était la titulaire. Par courrier du Cycle du 10 octobre 1997, X._ a été informé que, à la suite de plaintes émanant de parents d'élèves du cours de français de la classe xxx, une enquête allait être ouverte et qu'il serait entendu dans le cadre de celle-ci. Cette information a été confirmée le 13 octobre 1997, lors d'une séance réunissant le Président de la Commission scolaire, le Directeur du Collège D._ et X._, qui a alors été entendu. A cette occasion, ce dernier a remis, en l'expliquant et le commentant, un document écrit contestant tous les griefs qui lui étaient adressés. Il a en outre répondu à différentes questions. Le 15 octobre 1997, le Département valaisan de l'éducation, de la culture et du sport (ci-après: le Département) a suspendu X._ de ses fonctions durant la procédure administrative. Le 17 novembre 1997, X._ a été entendu, en présence de son conseil, par la Commission d'enquête constituée entre-temps. II a derechef contesté tous les griefs qui lui étaient adressés. Le 22 décembre 1997, le dossier a été communiqué au conseil de X._, qui a produit des déterminations et requis différentes mesures d'instruction. Par décision du 27 mars 1998, le Conseil d'administration du Cycle a résilié avec effet immédiat l'engagement de X._ en qualité de maître de l'enseignement secondaire du premier degré, sous réserve d'homologation par le Département. Tenant pour constant que X._ avait des problèmes de santé qui l'obligeaient à avoir pendant les cours un comportement qui pouvait être compris par les élèves comme des actes de masturbation, le Conseil d'administration du Cycle a vu là un élément objectif conduisant l'employeur à ne plus pouvoir admettre la continuation des rapports de travail. Le Conseil d'administration du Cycle a aussi retenu que X._ ne créait ni ne maintenait, avec les parents et l'autorité scolaire, les contacts et la collaboration qu'on était en droit d'attendre de lui; en outre, il ne vouait pas à certains élèves l'attention spéciale qu'ils méritaient, il inspirait de la crainte à ses élèves, il tenait des propos et utilisait des textes à connotation raciste ou susceptibles d'être interprétés comme tels et il s'adonnait pendant les cours à la lecture de journaux ou à la préparation d'autres cours. Tous ces éléments constituaient des violations manifestes des obligations incombant à X._, de sorte qu'une continuation des rapports de service devenait intolérable. Le 2 avril 1998, le Département a approuvé la décision prise le 27 mars 1998 par le Conseil d'administration du Cycle. B. X._ a alors porté sa cause devant le Conseil d'Etat du canton du Valais (ci-après: le Conseil d'Etat) qui a rejeté le recours par décision du 15 septembre 2004. Le Conseil d'Etat a repris en substance l'argumentation du Conseil d'administration du Cycle. C. X._ a recouru contre la décision du Conseil d'Etat du 15 septembre 2004 auprès de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) qui l'a débouté, par arrêt du 11 mars 2005. Procédant à une appréciation anticipée des preuves, le Tribunal cantonal a renoncé à donner suite aux réquisitions d'instruction formulées par l'intéressé. Il a confirmé que les pièces du dossier montraient que X._ avait manqué à ses devoirs élémentaires d'enseignant, à quoi s'ajoutait le comportement équivoque de l'intéressé quant à ses problèmes de santé. II a enfin rejeté le grief de violation du droit d'être entendu. D. Agissant par la voie du recours de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du Tribunal cantonal du 11 mars 2005. Il invoque les art. 9, 29 al. 2 et 36 al. 3 Cst. Il se plaint en substance d'arbitraire, dans la constatation des faits et dans l'appréciation des preuves, ainsi que de violations du droit d'être entendu et du principe de la proportionnalité. Le Tribunal cantonal a renoncé à se déterminer sur le recours. Le Conseil d'Etat conclut au rejet du recours. E. Par ailleurs, au mois de décembre 1997, X._ a fait l'objet d'une plainte pénale pour avoir mêlé un enfant de moins de 16 ans à un acte d'ordre sexuel. II résulte du dossier que la justice pénale a considéré comme acquis que l'intéressé s'était livré en classe à des actes d'onanisme mais qu'il a été acquitté, seul le dol éventuel pouvant être retenu contre lui (cf. arrêt 6S.175/2003 du 7 août 2003, consid. 2 et 3).