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.

Considérant en droit:
1. Le Tribunal fédéral examine d'office (<ref-law>) et librement la recevabilité des recours qui sont déposés devant lui (<ref-ruling> consid. 1 p. 24 et les références citées).
1.1 Le recours est dirigé contre une décision rendue dans une cause de droit public (cf. <ref-law>) par une autorité cantonale de dernière instance (cf. art. 86 al. 1 lettre d LTF). Une autorité intercantonale telle que la Commission de recours constitue en effet une autorité cantonale au sens de cette disposition (arrêt 2C_361/2010 du 13 juillet 2010 consid. 1.3.1; Yves Donzallaz, Loi sur le Tribunal fédéral, 2008, no 3001, avec renvoi à Hansjörg Seiler, in Bundesgerichtsgesetz, 2007, no 10 ad <ref-law>). Cette autorité précède immédiatement le Tribunal fédéral, puisque l'art. 10 al. 2 3e phrase de l'Accord intercantonal prévoit que la décision d'une telle commission de recours peut faire l'objet d'un recours en matière de droit public en vertu de l'<ref-law>. Le recours devant le Tribunal administratif fédéral n'est pas ouvert (cf. art. 86 al. 1 let. d in fine LTF): selon l'art. 33 de la loi fédérale du 17 juin 2005 sur le Tribunal administratif fédéral (LTAF; RS 173.32), les décisions d'autorités cantonales ne peuvent être déférées à ce dernier que si une (autre) loi fédérale le prévoit, ce qui n'est pas le cas en l'espèce.
En outre, la Commission de recours présente les caractéristiques d'un tribunal supérieur au sens de l'<ref-law>. Selon la jurisprudence, en effet, on entend par là une autorité judiciaire cantonale dont les décisions ne sont pas susceptibles d'un recours ordinaire sur le plan cantonal et qui ne dépend pas du point de vue hiérarchique d'une autre autorité judiciaire cantonale (<ref-ruling> consid. 4.1 p. 97 s.; <ref-ruling> consid. 3.5 p. 135). Si le droit cantonal n'institue qu'une seule instance judiciaire - l'<ref-law> n'imposant pas la double instance de recours dans les causes de droit public (<ref-ruling> consid. 4.1 p. 97) -, celle-ci pourra être considérée comme un tribunal supérieur, à la condition qu'elle réponde aux exigences d'indépendance requises d'une autorité judiciaire et qu'elle ait le pouvoir d'examiner librement les faits et d'appliquer d'office le droit déterminant conformément à l'<ref-law> (arrêt 1C_434/2009 du 1er mars 2010 consid. 4.2; cf. aussi <ref-ruling> consid. 2.1).
En l'occurrence, la Commission de recours connaît notamment des recours de particuliers contre les décisions de l'autorité de reconnaissance, à savoir la CDIP (art. 10 al. 2 en relation avec l'art. 4 al. 1 de l'Accord intercantonal), qui agit par son Secrétariat général. Elle comprend au minimum 15 membres nommés conjointement par le Comité de la CDIP et le Comité de la CDS (art. 2 al. 1 du règlement de la Commission de recours de la CDIP et de la CDS du 6 septembre 2007, recueil systématique de la législation intercantonale dans le domaine de l'éducation no 4.1.1.2; ci-après: le règlement de la Commission de recours). Le Comité de la CDIP et le (la) secrétaire général(e) sont tous deux nommés par l'Assemblée plénière de la CDIP (cf. art. 7 al. 2 lettre a des Statuts de la CDIP, recueil systématique de la législation intercantonale dans le domaine de l'éducation no 2.1.1). Le Comité - organe de nomination de la Commission de recours - et le Secrétariat général - dont cette commission revoit les décisions - sont ainsi indépendants l'un de l'autre, ce qui évite que la Commission de recours soit confrontée à des conflits d'intérêts. Au surplus, l'art. 3 al. 1 du règlement de la Commission de recours prévoit expressément que les membres de celle-ci sont indépendants dans l'exercice de leur fonction. Par ailleurs, la Commission de recours examine librement les faits et applique le droit d'office (cf. art. 12 et 49 de la loi fédérale du 20 décembre 1968 sur la procédure administrative [RS 172.021], applicables par renvoi de la loi sur le Tribunal administratif fédéral [art. 37], à laquelle renvoient l'art. 10 al. 2 de l'Accord intercantonal, ainsi que l'art. 9 du règlement de la Commission de recours). Dans ces conditions, la Commission de recours satisfait aux exigences rappelées ci-dessus.
1.2 Aucune des exceptions énumérées à l'<ref-law> n'est réalisée en l'occurrence. Le cas d'espèce ne tombe en particulier pas sous le coup de l'art. 83 lettre t LTF, puisque le litige porte sur la reconnaissance d'une autorisation d'enseigner, et non sur le résultat d'examens ou d'autres évaluations des capacités (cf. arrêt 2C_416/2008 du 30 octobre 2008 consid. 1.1 non publié aux <ref-ruling>).
1.3 En raison de l'effet dévolutif du recours à la Commission de recours (cf. <ref-ruling> consid. 2a p. 302 s.), dont la décision - de dernière instance cantonale - peut seule être attaquée devant le Tribunal fédéral (cf. art. 86 al. 1 lettre d LTF), les conclusions du recourant sont irrecevables dans la mesure où elles se rapportent à la décision de la Conférence des directeurs du 26 septembre 2008.
1.4 Au surplus, le recours a été interjeté par une partie directement touchée par la décision attaquée et qui a un intérêt digne de protection à son annulation ou sa modification (cf. <ref-law>). Il a de plus été déposé en temps utile (cf. <ref-law>) et en la forme prévue par la loi (cf. <ref-law>), de sorte qu'il est en principe recevable.
2. Selon son art. 1er, intitulé "But", l'Accord intercantonal - auxquels tous les cantons ont adhéré - règle notamment la reconnaissance des diplômes cantonaux de fin d'études. Il favorise le libre accès aux cycles de formation supérieure et à l'exercice de la profession et contribue à assurer des formations de qualité dans toute la Suisse (art. 1 al. 3). Aux termes de l'art. 2, l'Accord s'applique à toutes les formations et à toutes les professions qui sont réglementées par les cantons.
La CDIP, en tant qu'autorité de reconnaissance (art. 4 al. 1 de l'Accord), émet les règlements de reconnaissance qui fixent, pour chaque diplôme de fin d'études ou pour des catégories de diplômes, notamment les conditions et la procédure de reconnaissance (art. 6 al. 1 lettres a et b et al. 2 de l'Accord). Les conditions de reconnaissance énoncent les exigences minimales auxquelles le diplôme de fin d'études doit satisfaire (art. 7 al. 1 de l'Accord). Les règlements doivent mentionner les qualifications attestées par le diplôme ainsi que la manière dont ces qualifications sont évaluées (art. 7 al. 2 de l'Accord). Ils peuvent contenir des prescriptions relatives à la durée de la formation, aux conditions d'accès à celle-ci, aux contenus de l'enseignement ainsi qu'aux qualifications du personnel enseignant (art. 7 al. 3 de l'Accord). Selon l'art. 8 de l'Accord, intitulé "Effets de la reconnaissance", la reconnaissance atteste que le diplôme de fin d'études satisfait aux conditions stipulées dans l'Accord et dans le règlement de reconnaissance spécifique (al. 1). Les cantons parties à l'Accord garantissent aux titulaires d'un diplôme reconnu le même droit d'accès aux professions réglementées sur le plan cantonal que celui accordé à leurs propres ressortissants au bénéfice d'un diplôme de fin d'études correspondant (al. 2).
En l'espèce, les règlements de reconnaissance entrant en ligne de compte sont le règlement du 26 août 1999 concernant la reconnaissance des diplômes de hautes écoles pour les enseignantes et enseignants du degré secondaire I (recueil systématique de la législation intercantonale dans le domaine de l'éducation no 4.2.2.4) ainsi que le règlement du 4 juin 1998 concernant la reconnaissance des diplômes d'enseignement pour les écoles de maturité (recueil systématique de la législation intercantonale dans le domaine de l'éducation no 4.2.2.1).
3. 3.1 Aux termes de l'art. 95 al. 2 Cst., la Confédération veille à créer un espace économique suisse unique. Elle garantit aux personnes qui justifient d'une formation universitaire ou d'une formation fédérale, cantonale ou reconnue par le canton la possibilité d'exercer leur profession dans toute la Suisse. Selon la disposition transitoire de l'art. 196 ch. 5 Cst., jusqu'à l'adoption d'une législation, les cantons sont tenus à la reconnaissance réciproque des titres sanctionnant une formation. L'Accord intercantonal contribue à l'exécution de cette obligation (cf. Herbert Plotke, Schweizerisches Schulrecht, 2e éd., 2003, p. 500).
3.2 Comme l'indique son préambule, la loi fédérale sur le marché intérieur repose notamment sur l'art. 95 Cst. Selon son art. 1er, unique disposition de la Section 1 intitulée "But et objet", cette loi garantit à toute personne ayant son siège ou son établissement en Suisse l'accès libre et non discriminatoire au marché afin qu'elle puisse exercer une activité lucrative sur tout le territoire suisse (al. 1). D'après l'al. 3, dans sa nouvelle teneur du 16 décembre 2005, on entend par activité lucrative "toute activité non régalienne ayant pour but un gain" ("jede nicht hoheitliche, auf Erwerb gerichtete Tätigkeit"; "ogni attività a scopo di lucro, eccetto quelle che rientrano negli ambiti di sovranità dello Stato"). La nouvelle définition comprend les activités exercées dans le cadre de rapports de droit public qui ne relèvent pas de la puissance publique et peuvent ainsi aussi être offertes sur le marché, telles que l'enseignement dans une école publique (cf. Message du 24 novembre 2004 relatif à la révision de la loi sur le marché intérieur, FF 2005 439 ch. 2.6; Thomas Zwald, Das Bundesgesetz über den Binnenmarkt, in Allgemeines Aussenwirtschafts- und Binnenmarktrecht, 2007, p. 418 no 29).
La loi sur le marché intérieur vise en particulier à faciliter la mobilité professionnelle et les échanges économiques en Suisse, à soutenir les efforts des cantons visant à harmoniser les conditions d'autorisation d'accès au marché, à accroître la compétitivité de l'économie suisse et à renforcer la cohésion économique de la Suisse (<ref-law>).
L'<ref-law> énonce le principe de la liberté d'accès au marché ainsi que ses implications. Sous le titre "Restrictions à la liberté d'accès au marché", l'<ref-law> définit les conditions auxquelles de telles restrictions sont admissibles. Aux termes de l'<ref-law>, les décisions relatives aux restrictions doivent faire l'objet d'une procédure simple, rapide et gratuite.
Intitulé "Reconnaissance des certificats de capacité", l'<ref-law> dispose ce qui suit:
"1 Les certificats de capacité cantonaux ou reconnus au niveau cantonal et permettant d'exercer une activité lucrative sont valables sur tout le territoire suisse pour autant qu'ils ne fassent pas l'objet de restrictions au sens de l'art. 3.
2 ... (abrogé)
3 Si le certificat de capacité ne répond que partiellement aux exigences en vigueur au lieu de destination, l'intéressé peut apporter la preuve qu'il a acquis les connaissances requises d'une autre manière dans le cadre d'une formation ou d'une activité pratique.
3bis La reconnaissance de certificats de capacité pour les activités lucratives couvertes par l'accord du 21 juin 1999 entre la Confédération suisse, d'une part, et la Communauté européenne et ses Etats membres, d'autre part, sur la libre circulation des personnes est régie par cet accord.
4 Lorsque les cantons prévoient la reconnaissance mutuelle des certificats de capacité dans un accord intercantonal, les dispositions de ce dernier l'emportent sur la présente loi."
L'ancien al. 2 avait la teneur suivante:
"En cas de restrictions au sens de l'article 3, l'intéressé a droit à l'examen, selon une procédure simple, rapide et gratuite, de la question de son libre accès au marché sur la base de son certificat de capacité".
Le Tribunal fédéral a interprété cette disposition en ce sens que les exigences de simplicité, de rapidité et de gratuité valaient de manière générale pour la procédure, et non seulement lorsque des restrictions au sens de l'art. 3 étaient envisagées (<ref-ruling> consid. 5b p. 63). Elle s'appliquait au surplus seulement à la procédure de première instance, à l'exclusion de la procédure de recours (arrêt 2P.362/1998 du 6 juillet 1999 consid. 5, in SJ 2000 I p. 177).
L'al. 2 de l'<ref-law> a été abrogé lors la révision du 16 décembre 2005: celle-ci a étendu les exigences en question, qui n'existaient que pour la procédure tendant à la reconnaissance d'un certificat de capacité (ancien al. 2 en question), à l'ensemble des procédures portant sur les restrictions d'accès au marché, en ajoutant un nouvel alinéa à l'art. 3 (al. 5 du projet, devenu al. 4; FF 2005 442, 462).
Un certificat de capacité au sens de l'<ref-law> est un document établi par une autorité cantonale ou un établissement dépendant du canton ou reconnu par lui, qui atteste l'aptitude de quelqu'un à exercer une activité lucrative déterminée (<ref-ruling> consid. 2b/bb p. 318). Cette aptitude suppose un certain niveau de formation relativement à l'activité en cause, formation qui peut découler d'un enseignement théorique portant sur les connaissances nécessaires à l'exercice de l'activité ou d'une expérience pratique dans l'exercice de celle-ci (Manuel Bianchi della Porta, in Commentaire romand, Droit de la concurrence, 2002, nos 9 à 11 ad <ref-law>). La prise en compte de l'expérience pratique ressort d'ailleurs de l'art. 4 al. 3 in fine LMI.
L'al. 3bis a été introduit par la novelle du 16 décembre 2005. Il s'agissait d'éviter que, à la suite de l'entrée en vigueur de l'accord du 21 juin 1999 entre la Confédération suisse, d'une part, et la Communauté européenne et ses Etats membres, d'autre part, sur la libre circulation des personnes (ALCP; RS 0.142.112.681; entré en vigueur le 1er juin 2002), des ressortissants suisses ne soient discriminés du fait que les règles internes régissant la reconnaissance au plan suisse des certificats de capacité cantonaux seraient moins favorables que celles de l'accord en question (FF 2005 422, 437 s. ch. 2.3, 443). Une telle discrimination était toutefois déjà prohibée par l'<ref-law> - selon lequel toute personne ayant son siège ou son établissement en Suisse a, en ce qui concerne l'accès au marché, des droits identiques à ceux qui sont accordés par la Confédération à des personnes étrangères dans des accords internationaux -, de sorte que l'introduction de l'al. 3bis repose aussi sur d'autres motifs, à savoir la volonté d'uniformiser les règles de reconnaissance et de faciliter par là leur mise en oeuvre (Zwald, op. cit., p. 445 note de bas de page 178).
Selon l'al. 3bis, l'accord sur la libre circulation des personnes régit aussi la reconnaissance au plan suisse des certificats de capacité cantonaux, pour autant que ces derniers se rapportent à des activités lucratives visées par cette convention. Le point déterminant est en effet de savoir si l'activité lucrative concernée - et non le certificat de capacité exigé pour exercer celle-ci, dont la reconnaissance est en cause - entre dans le champ d'application de l'accord (FF 2005 443). Lors de l'introduction de l'al. 3bis, la réserve de l'al. 4 en faveur des accords intercantonaux a été maintenue - contrairement à ce qui était prévu initialement - dans l'idée que ces accords sont plus favorables, dès lors qu'ils instituent une reconnaissance automatique des certificats (FF 2005 422, 435 ch. 1.4.2.5; Zwald, op. cit., p. 436 note de bas de page 127).
La loi sur le marché intérieur connaît ainsi trois régimes de reconnaissance des certificats de capacité: celui des accords intercantonaux, celui de l'accord sur la libre circulation des personnes et celui de l'art. 4 al. 1 et 3 LMI, dont la portée a certes été considérablement restreinte par l'introduction de l'al. 3bis (FF 2005 443; Zwald, op. cit., p. 431 no 81).
L'<ref-law>, intitulé "Marchés publics", dispose que les marchés publics des cantons, des communes et des autres organes assumant des tâches cantonales ou communales sont régis par le droit cantonal ou intercantonal (al. 1). Ces prescriptions, ainsi que les décisions fondées sur elles, ne doivent pas discriminer les personnes ayant leur siège ou leur établissement en Suisse d'une manière contraire à l'art. 3 (al. 2).
Le droit intercantonal pertinent consiste notamment en l'accord intercantonal sur les marchés publics des 25 novembre 1994/15 mars 2001 (AIMPu; celui-ci est disponible sur le site Internet de la Conférence suisse des directeurs cantonaux des travaux publics, de l'aménagement du territoire et de l'environnement, à l'adresse www.dtap.ch), auxquels tous les cantons avaient adhéré au 1er juin 2009.
Ainsi, dans le domaine des marchés publics, l'art. 5 al. 1 2ème phrase LMI règle les rapports entre le droit intercantonal - notamment - et la loi sur le marché intérieur, en disposant que celui-là ne doit pas contrevenir à l'<ref-law>. S'agissant en revanche de la reconnaissance des certificats de capacité, l'<ref-law> se limite à prévoir que s'il existe un accord intercantonal, les dispositions de celui-ci l'emportent sur la loi sur le marché intérieur. Il ne dit rien de plus sur les rapports existant entre les deux, question qu'il y a lieu d'examiner à présent.
3.3 Les rapports entre les accords intercantonaux au sens des art. 4 al. 4 et 5 al. 1 LMI et la loi sur le marché intérieur ont été abondamment évoqués lors des travaux préparatoires de cette dernière, en particulier lors des débats parlementaires sur l'entrée en matière. Il en ressort que, dans leur domaine, les accords intercantonaux l'emportent sur la loi, pour autant qu'ils réalisent les objectifs de celle-ci. La loi s'applique de manière subsidiaire, dans la mesure où l'accord intercantonal concerné est lacunaire - dans ce cas, la loi vaut à titre supplétif, en complétant l'accord - ou contrevient à ses principes, qui constituent des exigences minimales à respecter par les cantons (Conseiller national Strahm, rapporteur de langue allemande, BO 1995 CN 1144; Conseillers nationaux Jaeger, Gros, Spoerry, BO 1995 CN 1147-1149; Conseillère aux Etats Simmen, rapporteur de langue allemande, BO 1995 CE 871; Conseiller fédéral Delamuraz, BO 1995 CN 1154, BO 1995 CE 873). Ainsi, s'agissant de la reconnaissance des certificats de capacité, le principe de l'art. 4 al. 1 et 3 LMI, à savoir leur reconnaissance sur tout le territoire suisse, sous réserve des restrictions prévues par l'<ref-law>, s'appliquait - c'était avant l'introduction de l'al. 3bis - en présence de certificats qui n'étaient pas réglementés par l'accord intercantonal ou qui l'étaient, mais pas dans le sens de la loi (FF 1994 I 1247 ch. 2.2.3; cf. aussi p. 1233 et 1235 ch. 154.2, où il est dit que les accords intercantonaux doivent satisfaire aux exigences minimales de la LMI). Certains intervenants se sont exprimés plus particulièrement au sujet de l'accord intercantonal, en relevant que celui-ci ne vise que certains diplômes (Conseiller fédéral Delamuraz, BO 1995 CN 1155; Conseiller national David, BO 1995 CN 1152) et ne contient pas de clause générale sur la reconnaissance des diplômes (Conseillère nationale Spoerry, BO 1995 CN 1149; Conseiller aux Etats Büttiker, BO 1995 CE 871 s.). La loi sur le marché intérieur devait ainsi s'appliquer de manière subsidiaire. Comparé à l'accord intercantonal sur les marchés publics, celui sur la reconnaissance des diplômes de fin d'études apparaissait toutefois relativement complet et abouti s'agissant de l'objectif de non-discrimination. L'accord sur les marchés publics était quant à lui trop limité, en ne prévoyant l'ouverture de ces marchés aux entreprises extérieures qu'à partir d'une valeur-seuil de 10 millions de fr. et en laissant la porte ouverte à des discriminations en-dessous de ce montant (Conseiller national David, BO 1995 CN 1152). C'est pour ce motif, apparemment, que l'interdiction des discriminations a été expressément mentionnée dans le contexte des marchés publics (<ref-law>), mais non dans celui de la reconnaissance des certificats de capacité (<ref-law>).
Lors de la révision de la loi sur le marché intérieur de 2005, le Conseiller aux Etats David, s'exprimant au nom de la commission de l'économie et des redevances, a de même relevé que la primauté des accords intercantonaux valait pour autant que ceux-ci instaurent une règlementation plus favorable que celle de l'accord sur la libre circulation des personnes, qui devenait applicable, selon le nouvel al. 3bis de l'<ref-law>, aussi à la reconnaissance des certificats de capacité au plan interne. En vertu de l'<ref-law>, qui prohibait toute discrimination des nationaux, il fallait en effet que les accords intercantonaux accordent au moins autant de droits, s'agissant de l'accès au marché, que les accords internationaux (BO 2005 CE 764).
D'après la doctrine également, la loi sur le marché intérieur s'applique de manière subsidiaire à l'Accord intercantonal (Vallender/Hettich/ Lehne, Wirtschaftsfreiheit und begrenzte Staatsverantwortung, 4e éd., 2006, § 14 no 38, qui précisent toutefois que cet accord satisfait apparemment aux exigences minimales de la loi). La loi s'applique notamment lorsqu'un certificat de capacité n'a pas fait l'objet d'un règlement de reconnaissance au sens de l'Accord intercantonal (Bianchi della Porta, op. cit., no 37 ad <ref-law>, avec renvoi à Karl Weber, Das neue Binnenmarktgesetz, RSDA 1996 p. 168).
Il ressort ainsi tant des travaux préparatoires que de la doctrine que l'Accord intercantonal prévaut sur la loi, pour autant qu'il en respecte les principes, qui constituent des exigences minimales. Cela vaut d'autant plus à la suite de la révision du 16 décembre 2005, qui visait à améliorer le fonctionnement du marché intérieur (cf. <ref-ruling> consid. 5.2 p. 333; <ref-ruling> consid. 2.1 p. 17).
4. 4.1 Selon l'<ref-law>, les parties contractantes prennent les mesures nécessaires, conformément à l'annexe III, en ce qui concerne notamment la reconnaissance mutuelle des diplômes, certificats et autres titres.
Intitulée "Reconnaissance mutuelle des qualifications professionnelles", l'annexe III ALCP se réfère à trois sortes de directives européennes (cf. Frédéric Berthoud, Die Anerkennung von Berufsqualifikationen zwischen der Schweiz und der EU, in Bilaterale Verträge I & II Schweiz - EU, 2007, p. 257 no 30 [cité: Anerkennung]; idem, Commentaire de l'<ref-ruling>, PJA 2009 p. 515 s. [cité: Commentaire]; Nina Gammenthaler, Die schweizerische Rechtsprechung zur Diplomanerkennung im Rahmen des FZA, Annuaire suisse de droit européen 2008/2009, p. 422 s.):
- des directives (au nombre de douze) spécifiques à certaines professions (métiers de la santé notamment) qui harmonisent la formation et prévoient la reconnaissance automatique des diplômes délivrés au terme de la formation de base;
- deux directives générales qui ne prévoient pas une reconnaissance automatique - les formations n'étant pas harmonisées -, mais instituent une procédure de reconnaissance consistant à établir l'équivalence des formations et, en cas de différences substantielles, à exiger une épreuve d'aptitude ou un stage d'adaptation: la Directive 89/48/ CEE du Conseil, du 21 décembre 1988, relative à un système général de reconnaissance des diplômes d'enseignement supérieur qui sanctionnent des formations professionnelles d'une durée minimale de trois ans (JO L 19 du 24 janvier 1989 p. 16) et la Directive 92/51/CEE du Conseil, du 18 juin 1992, relative à un deuxième système général de reconnaissance des formations professionnelles, qui complète la Directive 89/48/CEE (JO L 209 du 24 juillet 1992 p. 25);
- la Directive 99/42/CE du Parlement européen et du Conseil du 7 juin 1999 instituant un mécanisme de reconnaissance des diplômes pour les activités professionnelles couvertes par les directives de libéralisation et portant mesures transitoires, et complétant le système général de reconnaissance des diplômes (JO L 2001 du 31 juillet 1999 p. 77); cette directive vise les professions - relevant essentiellement de l'industrie ou des arts et métiers - ne nécessitant pas de formation spécifique; elle permet d'obtenir une autorisation d'exercer une telle profession, moyennant la reconnaissance de l'expérience acquise dans celle-ci (Berthoud, Anerkennung, op. cit., p. 268 s. nos 65 ss; FF 2005 443 note de bas de page 14).
Au sein de l'Union européenne, l'ensemble de ces textes a été remplacé par la nouvelle Directive 2005/36/CE du Parlement européen et du Conseil du 7 septembre 2005 relative à la reconnaissance des qualifications professionnelles (JO L 255 du 30 septembre 2005 p. 22), qui reprend pour l'essentiel le système en vigueur jusque-là (Berthoud, Anerkennung, op. cit., p. 270 nos 74 s.). L'annexe III ALCP n'ayant pas encore été modifiée en conséquence, les anciennes directives demeurent applicables dans le cadre de l'accord sur la libre circulation des personnes (cf. <ref-law>).
Au surplus, en vertu de l'<ref-law>, il y a lieu de tenir compte de la jurisprudence de la Cour de justice des Communautés européennes antérieure à la date de la signature de l'accord. Selon cette jurisprudence, lorsque la reconnaissance du diplôme ou du certificat en cause n'est pas réglée dans les directives, l'autorité saisie d'une demande d'autorisation d'exercer une profession réglementée doit, sur la base des dispositions des traités constitutifs des Communautés européennes puis de l'Union européenne, examiner dans quelle mesure les connaissances et qualifications attestées par les documents produits correspondent à celles qui sont exigées pour exercer cette profession dans l'Etat membre d'accueil. Lorsque la comparaison montre que la correspondance n'est que partielle, l'autorité peut exiger du requérant qu'il établisse avoir acquis les connaissances et qualifications manquantes par une formation additionnelle, des examens complémentaires ou une expérience pratique (cf. <ref-ruling> consid. 9.4 p. 36 s. et la jurisprudence citée; Berthoud, Anerkennung, op. cit., p. 260 ss et les arrêts cités). La jurisprudence ne s'est au demeurant pas prononcée sur la question des émoluments de la procédure de reconnaissance (Berthoud, Anerkennung, op. cit., p. 263 no 44).
En vertu des art. 9 et 16 par. 2 ALCP, le système européen de reconnaissance des diplômes est directement applicable en Suisse (<ref-ruling> consid. 2.1 p. 344).
4.2 Les règles du droit européen ne prévoient la reconnaissance des diplômes, certificats et autres titres que dans la mesure où cela est nécessaire à l'exercice d'une profession, en vue de réaliser la libre circulation des personnes et des services, dans un Etat membre autre que celui où les qualifications professionnelles ont été acquises (voir le préambule des Directives 89/48/CEE et 92/51/CEE).
Il s'ensuit que ces règles s'appliquent uniquement à la reconnaissance des diplômes, certificats et autres titres à des fins professionnelles, à l'exclusion de leur reconnaissance à des fins académiques. La première a pour but l'exercice d'une profession dont l'accès est subordonné à une qualification, tandis que la seconde vise la poursuite des études, partant la mobilité des étudiants, et non des professionnels même si elle contribue à la favoriser. Si la première peut se fonder sur l'ensemble de la formation et de l'expérience du requérant, la seconde ne peut en principe être évaluée que par rapport à un seul titre de formation (<ref-ruling> consid. 7 p. 143; arrêt 2A.331/2002 du 24 janvier 2003, consid. 4; Berthoud, Anerkennung, op. cit., p. 254 nos 21 ss).
Il faut en outre que les diplômes, certificats et autres titres dont la reconnaissance est demandée permettent directement d'exercer la profession concernée (Max Wild, Die Anerkennung von Diplomen im Rahmen des Abkommens über die Freizügigkeit der Personen, in Accords bilatéraux Suisse - UE, 2001, p. 386).
Les règles européennes sur la reconnaissance des diplômes, certificats et autres titres ne sont applicables que lorsque l'intéressé veut exercer une activité professionnelle qui est réglementée dans l'Etat membre d'accueil. Par "activité professionnelle réglementée", il faut entendre une profession dont l'exercice est réservé aux titulaires d'un diplôme, certificat ou autre titre déterminé. Cette notion doit être distinguée de celle de "formation réglementée" (Berthoud, Anerkennung, op. cit., p. 252 s. nos 14 ss; idem, Commentaire, op. cit., p. 516; Gammenthaler, op. cit., p. 431 s.).
4.3 Parmi les directives générales, la Directive 89/48/CEE règle la reconnaissance des diplômes au sens de son art. 1er lettre a. La Directive 92/51/CEE connaît, outre la notion de diplôme, telle qu'elle est définie à son art. 1er lettre a, celles de certificat (art. 1er lettre b) et d'attestation de compétence (art. 1er lettre c). Une attestation de compétence peut notamment consister en un "titre délivré à la suite d'une appréciation des qualités personnelles, des aptitudes ou des connaissances du demandeur, considérées comme essentielles pour l'exercice d'une profession par une autorité désignée conformément aux dispositions législatives, réglementaires ou administratives d'un Etat membre, sans que la preuve d'une formation préalable ne soit requise" (art. 1er lettre c 2ème tiret). Au demeurant, dans la terminologie de langue allemande, les trois catégories ci-dessus (Diplom, Prüfungszeugnis, Befähigungsnachweis; sur ces notions, cf. pour le surplus Wild, op. cit., p. 388 ss) correspondent approximativement à celles qui figurent dans l'intitulé de l'<ref-law> ("Diplome, Zeugnisse und sonstige Befähigungsnachweise").
Selon Zwald (op. cit., p. 434 note de bas de page 116), les certificats de capacité cantonaux au sens de l'<ref-law> entrent essentiellement dans les catégories des certificats et des attestations de compétence, telles qu'elles sont définies par le droit européen.
5. 5.1 En l'occurrence, la reconnaissance des diplômes permettant d'exercer la profession d'enseignant aux niveaux secondaires I et II est régie par l'Accord intercantonal et les règlements d'application cités plus haut. Or, il est incontesté que, sur cette base, le recourant ne peut obtenir la reconnaissance au plan suisse des autorisations d'enseigner obtenues du canton de Neuchâtel le 22 juin 1998 et du canton de Fribourg le 17 avril 2008. L'Accord intercantonal ainsi que les règlements de reconnaissance pertinents prévoient en effet seulement la reconnaissance de diplômes de fin d'études, ce que les autorisations litigieuses ne sont pas.
La question est dès lors de savoir si le recourant peut obtenir la reconnaissance des autorisations en cause en vertu de la loi sur le marché intérieur. La Commission de la concurrence y répond par l'affirmative, alors que la Conférence des directeurs ainsi que le Département fédéral de l'économie sont d'avis contraire. Ces derniers font valoir pour l'essentiel qu'en vertu de l'<ref-law>, lorsque les cantons prévoient dans un accord intercantonal la reconnaissance mutuelle des certificats de capacité au sens des diplômes d'enseignement délivrés ou reconnus par eux, les dispositions de cet accord l'emportent sur celles de la loi fédérale. L'Accord intercantonal et ses règlements d'application régissant de manière exhaustive la reconnaissance au plan suisse des certificats de capacité dans le domaine de l'enseignement, il n'y aurait plus de place pour une application parallèle de la loi sur le marché intérieur. La reconnaissance au plan suisse des autorisations en question ne pourrait ainsi intervenir qu'en contournant la réglementation intercantonale, ce qui conduirait à mettre à néant "l'assurance qualité dans le domaine de la formation enseignante en Suisse" et à créer une inégalité de traitement par rapport aux titulaires d'un diplôme d'enseignement.
5.2 Comme indiqué plus haut (consid. 3.3), l'Accord intercantonal ne l'emporte sur la loi que pour autant qu'il en respecte les principes, qui constituent des exigences minimales. Ainsi, lorsque, comme en l'espèce, une demande de reconnaissance ne peut être admise sur la base de l'Accord intercantonal, il faut encore s'assurer que ce résultat soit conforme à la loi sur le marché intérieur. Il convient donc d'examiner si les autorisations en cause tombent sous le coup de cette loi et en particulier de son art. 4.
5.3 Le recourant demande la reconnaissance d'autorisations d'enseigner dans les écoles publiques au niveau secondaire. Or, comme indiqué plus haut (consid. 3.2), l'activité d'enseignant dans une école publique est une activité lucrative au sens de l'<ref-law>. Reste à savoir si ces autorisations constituent des certificats de capacité au sens de l'<ref-law>.
L'autorisation délivrée par le canton de Neuchâtel l'a été en vertu de l'art. 39 de la loi neuchâteloise sur l'organisation scolaire du 28 mars 1984 (RS/NE 410.10), aux termes duquel "le Conseil d'Etat peut exceptionnellement accorder l'autorisation d'enseigner à des personnes dont la compétence est reconnue" et après examen du dossier du recourant. Quant au document signé le 17 avril 2008 par la Conseillère d'Etat en charge de la Direction de l'instruction publique, de la culture et du sport du canton de Fribourg, il en ressort que la demande d'autorisation d'enseigner aux niveaux secondaires I et II dans le canton de Fribourg déposée par le recourant a été examinée par une délégation du Groupe de travail cantonal de reconnaissance de titres d'enseignement pour les écoles publiques du canton. Au terme de cet examen, le droit d'enseigner dans le canton de Fribourg - au niveau secondaire I et, pour la géographie seulement, au niveau secondaire II - a été reconnu sur la base des documents produits par le recourant, à savoir notamment la licence de l'Université de Neuchâtel, une "attestation concernant la formation didactique et les séminaires spéciaux suivis en 1997/98 au Séminaire pédagogique de l'enseignement secondaire (NE)" ainsi que l'autorisation d'enseigner du 22 janvier 1998. Il est encore précisé que, sur la base du document du 17 avril 2008, le recourant peut souscrire aux mises au concours de postes d'enseignement correspondants et que, si sa candidature est retenue, un "contrat qui équivaut à une autorisation formelle d'enseigner dans le canton de Fribourg" lui sera remis.
Les autorisations d'enseigner en question ont été établies par l'autorité cantonale compétente, après examen du dossier du recourant. Elles attestent l'aptitude de celui-ci à exercer l'activité lucrative d'enseignant au niveau secondaire (à tout le moins pour la géographie). Elles constituent, partant, des certificats de capacité au sens de l'<ref-law>. Peu importe qu'il s'agisse d'autorisations "exceptionnelles" laissées à la libre appréciation des cantons, auxquelles il n'existe pas de droit, à la différence de celles délivrées sur la base d'un diplôme (cf. à ce sujet Plotke, op. cit., p. 509 no 18.62).
La Conférence des directeurs voudrait que seuls les diplômes de fin d'études au sens de l'Accord intercantonal puissent être reconnus comme certificats de capacité d'enseigner. On ne voit toutefois pas pourquoi l'aptitude à enseigner pourrait découler seulement d'un enseignement théorique sanctionné par l'obtention d'un diplôme, à l'exclusion de l'expérience pratique, ce d'autant que l'art. 4 al. 3 in fine LMI prévoit expressément la prise en compte de cette dernière. Quant aux craintes de nivellement par le bas et d'inégalité de traitement par rapport aux titulaires d'un diplôme d'enseignement, elles sont largement infondées: d'une part, les cantons n'accordent assurément pas les autorisations exceptionnelles en question sans un examen sérieux du dossier; d'autre part, comme il n'existe par définition aucun droit à l'octroi de telles autorisations, les personnes se destinant à l'enseignement continueront dans leur très grande majorité à suivre une formation débouchant sur un diplôme d'enseignant.
Dès lors que les autorisations d'enseigner obtenues par le recourant constituent des certificats de capacité au sens de l'<ref-law>, qui au surplus permettent d'exercer une activité lucrative, la Conférence des directeurs et, à sa suite, la Commission de recours ne pouvaient rejeter la demande de reconnaissance litigieuse sur la seule base de l'Accord intercantonal. En effet, l'<ref-law> pose le principe selon lequel de tels certificats de capacité sont valables sur tout le territoire suisse, pour autant qu'ils ne fassent pas l'objet de restrictions au sens de l'<ref-law>. L'<ref-law> renvoie certes à l'accord sur la libre circulation des personnes, rendu applicable aussi à la reconnaissance au plan suisse de certificats de capacité pour les activités lucratives couvertes par celui-ci. Cette nouvelle disposition, introduite par la novelle du 16 décembre 2005, ne saurait toutefois conduire à limiter le principe de l'<ref-law>, du moment que la révision en question tendait au contraire à améliorer le fonctionnement du marché intérieur et le libre accès au marché (voir aussi Zwald, op. cit., p. 435 no 96, qui appelle les cantons à faire preuve de "souplesse" dans l'application des directives européennes, de manière à assurer un accès au marché le plus libre possible).
Il n'appartient pas au Tribunal fédéral d'examiner comme première et unique instance si, et le cas échéant à quelles conditions, le recourant peut prétendre, sur la base des règles exposées ci-dessus, à la reconnaissance au plan suisse des autorisations d'enseigner en cause. Cela vaut d'autant plus que le Tribunal de céans fait preuve d'une certaine retenue lorsque, comme en l'espèce, la résolution du cas suppose des connaissances techniques. Dans ces conditions, il convient d'annuler la décision entreprise et de renvoyer le dossier à la Conférence des directeurs pour qu'elle statue à nouveau dans le sens des considérants du présent arrêt.
Au surplus, la gratuité de la procédure prévue à l'<ref-law> constitue une exigence minimale de la loi sur le marché intérieur. Comme le Tribunal de céans l'a jugé en relation avec l'ancien al. 2 de l'<ref-law> (cf. consid. 3.2 ci-dessus), cette exigence vaut de manière générale pour les procédures relatives à l'accès au marché (cf. aussi Zwald, op. cit., p. 430 no 76). Le droit européen auquel renvoient les <ref-law> et 9 ALCP ne prescrit certes pas la gratuité de la procédure de reconnaissance (cf. consid. 4.1 ci-dessus). Toutefois, comme cela a été relevé en relation avec le principe de la validité des certificats de capacité au plan suisse (<ref-law>), la révision du 16 décembre 2005 ne tendait assurément pas non plus à remettre en cause le principe de la gratuité de la procédure. Par conséquent, ce principe s'impose aux cantons comme une exigence minimale, aussi lorsque ceux-ci règlent la reconnaissance des certificats de capacité dans un accord intercantonal, conformément à l'<ref-law> (cf. Bianchi della Porta, op. cit., no 37 ad <ref-law>). Il ne vaut en revanche pas pour la procédure de recours (<ref-ruling> consid. 7 p. 339 s.).
Dans le cas particulier, la Conférence des directeurs n'était ainsi pas fondée à percevoir un émolument lorsqu'elle a rendu sa décision du 26 septembre 2008. Sa nouvelle décision devra de même être rendue gratuitement.
6. Vu ce qui précède, le recours doit être admis dans la mesure où il est recevable, la décision attaquée annulée et la cause renvoyée à la Conférence des directeurs pour qu'elle statue à nouveau dans le sens des considérants du présent arrêt.
Il n'y a pas lieu de percevoir de frais de justice (cf. <ref-law>). Succombant, la Conférence des directeurs devra verser au recourant une indemnité à titre de dépens (cf. <ref-law>).
Le Tribunal fédéral ne fera pas usage de la faculté prévue aux art. 67 et 68 al. 5 LTF et renverra la cause à l'autorité précédente pour qu'elle statue sur les frais et dépens de la procédure suivie devant elle.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis dans la mesure où il est recevable. La décision de la Commission de recours CDIP/CDS du 23 octobre 2009 est annulée et la cause renvoyée à la Conférence suisse des directeurs cantonaux de l'instruction publique pour qu'elle statue à nouveau dans le sens des considérants du présent arrêt.
2. La cause est renvoyée à la Commission de recours CDIP/CDS afin qu'elle statue à nouveau sur le sort des frais et dépens de la procédure suivie devant elle.
3. Il n'est pas perçu de frais judiciaires.
4. La Conférence suisse des directeurs cantonaux de l'instruction publique versera au recourant une indemnité de 2'000 fr. à titre de dépens.
5. Le présent arrêt est communiqué au mandataire du recourant, à la Conférence suisse des directeurs cantonaux de l'instruction publique, à la Commission de recours CDIP/CDS, au Département fédéral de l'économie ainsi qu'à la Commission fédérale de la concurrence.
Lausanne, le 31 août 2010
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Zünd Vianin