Faits:
A. A.a P._ a travaillé en qualité d'agent spécialisé (chef de projet X._) pour l'Etat de Genève du 1er avril 2001 au 31 décembre 2008. Il a ensuite été engagé comme directeur du Service Y._ par le département du territoire, dès le 1er janvier 2009. Le 1er décembre 2009, il a été nommé fonctionnaire. A la fin de l'année 2009, le Service Y._ a été transféré au Département Z._ dans le cadre des remaniements départementaux.
Le 12 avril 2010, le Groupe de confiance a recommandé à la secrétaire générale du Département Z._ l'ouverture d'une enquête administrative à l'encontre de P._ afin de vérifier si le comportement reproché à ce dernier par certains membres de son service pouvait constituer des atteintes à la personnalité, voire du harcèlement psychologique.
Par arrêté du 1er juin 2010, le Conseil d'Etat a ordonné l'ouverture d'une enquête administrative à l'encontre de P._ et confié la conduite de celle-ci à C._, juge à la Cour de justice. Ce dernier a procédé à l'audition de P._ ainsi que de plusieurs témoins au cours de l'été 2010.
A.b Le 18 octobre 2010, M._, secrétaire au Service Y._, a été auditionnée par la Direction des ressources humaines (DRH) du Département Z._. Cet entretien a fait l'objet d'un compte-rendu du 21 octobre 2010. Le lendemain, P._ a écrit à la secrétaire générale du Département Z._. Il s'étonnait de ne pas avoir encore reçu copie du rapport d'enquête.
Au cours d'un entretien qui s'est tenu le 1er novembre 2010 en présence de membres de la DRH, la secrétaire générale du Département Z._ a informé P._ et son conseil qu'un complément d'enquête serait demandé en raison de l'apparition de faits nouveaux. S'adressant le même jour au Conseil d'Etat, P._ a demandé que le rapport d'enquête lui soit communiqué immédiatement. En cas de refus, une décision munie des voies de recours devait être rendue.
Par décision du 3 novembre 2010, le Conseil d'Etat a refusé de communiquer le rapport d'enquête à P._ jusqu'à l'établissement complet des faits par l'enquêteur. Par arrêté du même jour, le Conseil d'Etat a ordonné un complément d'enquête portant sur les faits à la base de nouvelles plaintes émises à l'encontre de P._ et invité l'enquêteur à établir d'office tous autres faits répréhensibles pouvant apparaître au cours de l'enquête complémentaire. Il a par ailleurs suspendu provisoirement l'intéressé de sa fonction, sans suspension de traitement.
A.c Le 11 novembre 2010, l'enquêteur a adressé au conseil de P._ une lettre dont la teneur essentielle est la suivante:
«Vous avez pu consulter, à votre demande, les pièces relatives à l'extension, sur faits nouveaux, de l'enquête administrative qui m'avait été confiée le 1er juin 2010. Compte tenu de la recommandation du Groupe de confiance, je n'entends pas procéder à l'audition de Mme M._ en la présence de M. P._ ni de celle de son défenseur. Je vous communique, par conséquent, copie du compte-rendu de l'entretien du 21 octobre 2010, en vous priant de me faire parvenir (...), la liste écrite des questions que votre client et vous souhaitez me faire poser à Mme M._. Quant aux autres pièces dont vous avez demandé la copie, je n'entends pas vous les délivrer. D'une part, à situation égale, vous n'aviez pas demandé de copies avant les auditions menées à la suite du premier arrêté du Conseil d'Etat; d'autre part, le Conseil d'Etat vous a rappelé, dans sa lettre du 3 novembre 2010, que votre client disposerait d'un délai de 30 jours pour présenter ses présentations sur le dossier qui aura été mis à votre disposition par l'Office du personnel, ce qui préserve le droit d'être entendu. Pour la même raison, M. P._ ne sera pas réentendu par mes soins».
Le 17 novembre 2010, P._ a sollicité du Conseil d'Etat la récusation de l'enquêteur. Il ressortait du courrier précité que C._ n'entendait pas respecter son droit d'être entendu. L'enquêteur ne respectait pas non plus les indications de Mme O._ (directrice, DRH) et du Conseil d'Etat selon lesquelles il aurait accès à toutes les pièces du dossier et pourrait pleinement s'exprimer. Quant à l'indication selon laquelle il n'avait jamais demandé des copies du dossier avant les auditions menées à la suite du premier arrêté du Conseil d'Etat, elle était totalement erronée. Tous ces éléments constituaient autant de circonstances de nature à faire suspecter la partialité de l'enquêteur.
B. Par arrêté du 7 décembre 2010, le Conseil d'Etat a notamment rejeté la demande de récusation. Même s'il pouvait paraître malencontreux, le courrier de l'enquêteur du 11 novembre 2010 ne démontrait aucune partialité de sa part. Les faits faisant l'objet de l'arrêté du 3 novembre 2010 relatifs au complément d'enquête administrative avaient été portés à la connaissance de P._, lequel avait pu s'exprimer lors de l'entretien du 1er novembre 2010 et avoir accès au dossier au greffe de la Cour de justice. Son droit d'accéder au dossier complètement instruit subsistait et il pourrait déposer des observations avant qu'une décision ne soit prise par le Conseil d'Etat.
C. Par jugement du 1er février 2011, la Chambre administrative de la Cour de justice a rejeté le recours interjeté par P._ contre l'arrêté du Conseil d'Etat du 7 décembre 2010, en tant qu'il portait sur la récusation de l'enquêteur.
D. P._ a formé contre ce jugement un recours en matière de droit public et un recours constitutionnel subsidiaire. Il a présenté une requête de restitution de l'effet suspensif et d'octroi de mesures provisionnelles tendant à faire interdiction à l'enquêteur de procéder, jusqu'à droit jugé par le Tribunal fédéral, à tout acte d'instruction. Sur le fond, il a conclu au prononcé par le Tribunal fédéral de la récusation de C._.
L'Office du personnel de l'Etat de Genève a conclu, au nom du Conseil d'Etat, au rejet tant de la requête d'effet suspensif que du recours.
E. Par ordonnance du 13 mai 2011, le juge délégué à l'instruction de la cause a rejeté la requête d'effet suspensif et de mesures provisionnelles.
F. Le 12 mai 2011, P._ a demandé au tribunal l'autorisation de répliquer. Par ordre du Président de la Ire Cour de droit social, la chancellerie du Tribunal fédéral lui a répondu qu'il ne se justifiait pas, en l'espèce, d'ordonner un échange ultérieur d'écritures. En revanche, les parties étaient libres de déposer spontanément toute nouvelle écriture. Le 7 juin 2011, P._ s'est prononcé sur le contenu de la détermination de l'Office du personnel de l'Etat.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1.1 p. 3; <ref-ruling> consid. 1 p. 444).
2. 2.1 Selon l'<ref-law>, les décisions préjudicielles et incidentes qui sont notifiées séparément et qui portent sur la compétence ou sur une demande de récusation peuvent faire l'objet d'un recours (al. 1). Ces décisions ne peuvent plus être attaquées ultérieurement (al. 2). Par leur nature, les questions concernant la compétence de l'autorité et sa composition régulière doivent en effet être tranchées préliminairement, de manière définitive, avant que ne se poursuive la procédure (BERNARD CORBOZ, in: Commentaire de la LTF, Berne 2009, n° 20 ad art. 92). En l'espèce, on est en présence d'une décision incidente qui porte sur la récusation et qui est donc susceptible de faire l'objet d'un recours immédiat. Bien que cette condition ne soit pas expressément prévue par la loi, il va par ailleurs de soi qu'en vertu du principe de l'unité de la procédure, le recours contre une décision incidente est exclu si le recours contre la décision finale n'est pas recevable (<ref-ruling> consid. 2.2 p. 647).
2.2 Au stade actuel de la procédure, aucune sanction n'a été prononcée à l'encontre du recourant. Rien ne dit au demeurant que le Conseil d'Etat pourrait être amené à prendre des sanctions disciplinaires susceptibles d'avoir une incidence directe sur le traitement du recourant. On doit donc admettre que l'exception prévue à l'art. 83 let. g LTF s'applique en l'espèce. Seule la voie du recours constitutionnel subsidiaire (<ref-law>) est ouverte. En tant que partie à la procédure cantonale, disposant de surcroît d'un intérêt juridique à l'annulation de la décision attaquée, le recourant a qualité pour agir au sens de l'<ref-law>.
3. 3.1 Le recourant invoque le droit à une autorité impartiale qu'il déduit de l'art. 29 al. 1 Cst. Il soutient qu'il ressort de la formulation et du contenu du courrier de l'enquêteur du 11 novembre 2010 une volonté délibérée de ce dernier de porter atteinte à ses droits procéduraux.
L'art. 29 al. 1 Cst. dispose que toute personne a droit, dans une procédure judiciaire ou administrative, à ce que sa cause soit traitée équitablement. Selon la jurisprudence, ce droit permet notamment d'exiger la récusation des membres d'une autorité administrative dont la situation ou le comportement sont de nature à faire naître un doute sur leur indépendance ou leur impartialité; il tend à éviter que des circonstances extérieures à l'affaire ne puissent influencer une décision en faveur ou au détriment de la personne concernée. La récusation peut s'imposer même si une prévention effective du membre de l'autorité visée n'est pas établie, car une disposition interne de sa part ne peut guère être prouvée; il suffit que les circonstances donnent l'apparence de la prévention et fassent redouter une activité partiale. Cependant, seules des circonstances constatées objectivement doivent être prises en considération; les impressions purement individuelles d'une des personnes impliquées ne sont pas décisives (<ref-ruling> consid. 2b p. 198; <ref-ruling> consid. 3b p. 123; arrêt 8C_639/2009 du 9 octobre 2009 consid. 5.1).
Parfois, l'autorité récusée n'a pas pour tâche de statuer dans la cause, mais d'assumer un rôle d'investigation. Tel est le cas d'un enquêteur chargé d'établir les faits dans le cadre d'une enquête administrative ouverte à l'encontre d'un fonctionnaire soupçonné d'avoir enfreint ses devoirs de service. Or, il n'est pas suspect de prévention du seul fait qu'il a commis une faute de procédure ou fait une fausse application du droit de fond. De telles erreurs doivent en principe être soulevées dans le cadre d'un recours contre la décision elle-même (cf. BENJAMIN SCHINDLER, Die Befangenheit der Verwaltung, 2002, p. 137). La récusation ne se justifie, selon la jurisprudence, que si l'enquêteur commet des erreurs de procédure ou d'appréciation particulièrement lourdes ou répétées, qui doivent être considérées comme des violations graves de ses devoirs et dénotent l'intention de nuire au fonctionnaire (ATF <ref-ruling> consid. 3e p. 124; <ref-ruling> consid. 3b p. 404; arrêt 1B_144/2009 du 4 juin 2009 consid. 2.2).
3.2 Devant le Tribunal fédéral, le recourant ne prétend plus que le refus de l'enquêteur de procéder à l'audition de Mme M._ en sa présence et/ou de son conseil constituait un motif de récusation. En revanche, il soutient que la décision restreignant l'accès aux pièces prise par l'enquêteur ainsi que son refus de le réentendre personnellement était de nature à faire suspecter de la partialité de l'enquêteur dès lors qu'ils avaient été pris sans aucun motif objectif.
3.3 L'enquêteur a justifié son refus, d'une part, par le fait que le recourant n'avait pas demandé de copies avant les auditions menées à la suite du premier arrêté du Conseil d'Etat et, d'autre part, par le fait que le Conseil d'Etat lui avait rappelé, dans sa décision du 3 novembre 2010, qu'il disposerait d'un délai de 30 jours pour déposer ses observations une fois que le rapport d'enquête lui aurait été communiqué. Si la première raison avancée par l'enquêteur paraît erronée à la lumière de l'affirmation du recourant selon laquelle il aurait obtenu, lors de la consultation du dossier au greffe de la Cour de justice durant la première partie de l'enquête, copie de toutes les pièces dont il ne disposait pas encore, cette simple erreur sur un fait ne suffit pas pour admettre un motif de prévention. En ce qui concerne le refus comme tel de l'enquêteur de communiquer les pièces au dossier, on relèvera, comme l'ont fait les premiers juges, que cette décision reposait sur une base légale et qu'elle pouvait a priori se justifier eu égard à la nature délicate de l'affaire opposant un cadre à ses subordonnés. Toujours est-il que le refus de l'enquêteur n'était pas définitif puisqu'il n'interdisait pas tout accès aux pièces mais ne visait qu'à en différer la consultation jusqu'au moment de l'issue de l'enquête. Si cette manière de faire devait se révéler contraire aux droits de procédure du recourant, elle ne serait en tous les cas pas suffisamment grave pour que l'on puisse y voir un parti pris hostile au recourant ni une opinion arrêtée sur les conclusions de l'enquête.
De même, on ne saurait considérer que le refus de réentendre le recourant témoigne d'une prévention de l'enquêteur dès lors que, selon les premiers juges, c'est sur la base des règles de procédure cantonales (cf. art. 27 al. 4 et 5 de la loi générale relative au personnel de l'administration cantonale, du pouvoir judiciaire et des établissements publics médicaux [LPAC]); RSG B 5 05) que celui-ci a pris cette décision. Or, celles-ci ne prévoient le droit qu'à une seule audition des parties et n'aménagent une seconde audition que si de nouveaux témoins sont entendus. A supposer qu'une incompatibilité de ces règles de procédure avec le droit d'être entendu du recourant dût être établie ultérieurement, celle-ci ne constituerait pas non plus une erreur suffisamment grave pour entraîner le récusation de l'enquêteur.
4. De ce qui précède, il résulte que le recours est mal fondé. Succombant, le recourant supportera les frais judiciaires (<ref-law>). Bien qu'il obtienne gain de cause, le Conseil d'Etat n'a pas droit à des dépens (<ref-law>; arrêt 8C_151/2010 du 31 août 2010 consid. 6.2).

Le Tribunal fédéral prononce:
1. Le recours en matière de droit public est irrecevable.
2. Le recours constitutionnel subsidiaire est rejeté.
3. Les frais judiciaires, arrêtés à 1500 fr., sont mis à la charge du recourant.
4. Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre administrative.
Lucerne, le 1er juillet 2011
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: La Greffière:
Ursprung Fretz Perrin