Faits: A. X._ est titulaire d'une licence en géographie, anglais et sciences de l'éducation de l'Université de Neuchâtel. Par arrêté du Conseil d'Etat du canton de Neuchâtel du 22 juin 1998, il a obtenu une autorisation d'enseigner la géographie aux degrés secondaires I et II dans ce canton. Le 3 janvier 2006, le prénommé a requis de la Conférence suisse des directeurs cantonaux de l'instruction publique (ci-après: la Conférence des directeurs) notamment la reconnaissance au niveau suisse de son autorisation d'enseigner. Le 17 avril 2008, X._ a été mis au bénéfice d'une autorisation d'enseigner dans le canton de Fribourg au niveau secondaire I, ainsi que, pour la géographie uniquement, au niveau secondaire II. B. Par décision du 26 septembre 2008, la Conférence des directeurs a refusé la reconnaissance sollicitée et mis un émolument de 100 fr. à la charge de X._. Saisie d'un recours contre ce prononcé, la Commission de recours de la Conférence suisse des directeurs cantonaux de l'instruction publique (CDIP) et de la Conférence suisse des directeurs cantonaux de la santé (CDS) - ci-après: la Commission de recours - l'a rejeté par décision du 23 octobre 2009. Elle a considéré qu'en vertu de l'accord sur la reconnaissance des diplômes de fin d'études du 18 février 1993 (recueil systématique de la législation intercantonale dans le domaine de l'éducation - il peut être consulté sur le site Internet de la Conférence des directeurs, à l'adresse www.edk.ch - no 4.1.1; ci-après: l'Accord intercantonal ou l'Accord) et de ses règlements d'application, seul un diplôme de fin d'études peut être reconnu. Or, en l'occurrence, X._ n'était pas au bénéfice d'un tel diplôme, mais seulement de deux autorisations d'enseigner, l'une dans le canton de Neuchâtel et l'autre dans celui de Fribourg. En outre, ces dispositions de droit intercantonal l'emportaient sur la loi fédérale du 6 octobre 1995 sur le marché intérieur (LMI; RS 943.02), de sorte que le recourant ne pouvait se prévaloir de cette dernière aux fins d'obtenir la reconnaissance des autorisations en question. C. Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler la décision du 23 octobre 2009 ainsi que celle du 26 septembre 2008 et de renvoyer la cause à la Conférence des directeurs, afin qu'elle reconnaisse les autorisations d'enseigner dont il bénéficie, et ce sans frais. Il se plaint de violations de l'Accord intercantonal et de ses règlements d'application, de la loi fédérale sur le marché intérieur, de l'interdiction de discrimination de l'art. 8 Cst. et de son droit d'être entendu. L'autorité précédente se réfère aux considérants de sa décision. La Conférence des directeurs conclut au rejet du recours, sous suite de frais. Le Département fédéral de l'économie propose également son rejet. La Commission de la concurrence se prononce en faveur de l'admission du recours. Dans une écriture du 10 mars 2010 faisant suite à l'envoi de la détermination de la Commission de la concurrence, la Conférence des directeurs a maintenu sa position.