Faits:
A. X._, né en 1959, d'origine algérienne, naturalisé suisse depuis 1998, est titulaire d'un diplôme de docteur en médecine délivré le 24 septembre 1983 à Alger et d'un certificat d'études spéciales (CES) relatives aux applications à la médecine des radio-éléments artificiels obtenu le 9 octobre 1986 à l'Université de Paris XII.
Le 23 décembre 2002, X._ a requis le Comité directeur des examens fédéraux pour les professions médicales (ci-après: le Comité directeur) de reconnaître son diplôme de docteur en médecine délivré à Alger et le Comité de la formation postgrade pour les professions médicales (ci-après: le Comité de la formation postgrade) de reconnaître son "certificat d'études spéciales en médecine nucléaire" délivré à Paris.
Par décisions séparées des 24 mars et 15 avril 2004, les Comités requis ont rejeté les demandes. En substance, le diplôme de docteur en médecine algérien n'avait pas été reconnu en France et le certificat d'études spéciales ne correspondait pas à une dénomination prévue par la directive 93/16/CEE du Conseil du 5 avril 1993.
Statuant par jugements séparés des 8 février et 3 mars 2005, la Commission fédérale de recours pour la formation de base et la formation postgrade des professions médicales (ci-après: la Commission fédérale de recours) a rejeté les recours formés par X._ contre les décisions des 24 mars et 15 avril 2004.
B. Agissant par la voie du recours de droit administratif, X._ a déposé deux mémoires de recours. Dans la procédure 2A.157/2005, il demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler le jugement du 8 février 2005 de la Commission fédérale de recours et de reconnaître son diplôme de docteur en médecine obtenu à Alger, subsidiairement de renvoyer le dossier au Comité directeur pour examen au sens des considérants de l'équivalence de ses compétences avec les connaissances et qualifications exigées par la législation suisse et, plus subsidiairement, de renvoyer le dossier à la Commission fédérale de recours pour examen au sens des considérants de l'équivalence de ses compétences avec les connaissances et qualifications exigées par la législation suisse.
Dans la procédure 2A.195/2005, il demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler le jugement du 3 mars 2005 de la Commission fédérale de recours et de reconnaître son diplôme de spécialiste en médecine nucléaire obtenu à Paris, subsidiairement de renvoyer le dossier au Comité de la formation postgrade pour examen au sens des considérants de l'équivalence de ses compétences avec les connaissances et qualifications exigées par la législation suisse et, plus subsidiairement, de renvoyer le dossier à la Commission fédérale de recours pour examen au sens des considérants de l'équivalence de ses compétences avec les connaissances et qualifications exigées par la législation suisse.
La Commission fédérale de recours conclut au rejet des deux recours.
Le 27 juillet 2005, X._ a déposé des contre-observations, confirmant ses conclusions.

Le Tribunal fédéral considère en droit:
1. Les deux recours sont dirigés contre des arrêts qui mettent en cause le même recourant et concernent tous deux la reconnaissance de diplômes étrangers dans le domaine médical. Il y a donc lieu de joindre les causes et de statuer par un seul arrêt (<ref-ruling> consid. 1 p. 60 s.).
2. Déposés en temps utile contre deux décisions fondées sur le droit public fédéral et prises par une commission fédérale de recours, sans qu'aucune des exceptions prévues aux art. 99 à 102 OJ ou dans la législation spéciale ne soit réalisée, les présents recours sont en principe recevables comme recours de droit administratif en vertu des art. 97 ss OJ (<ref-ruling> consid. 1.1 p. 60; <ref-ruling> consid. 3.1 p. 186).
3. Conformément à l'art. 104 lettre a OJ, le recours de droit administratif peut être formé pour violation du droit fédéral, y compris l'excès et l'abus du pouvoir d'appréciation (<ref-ruling> consid. 1.2.1). Le Tribunal fédéral revoit d'office l'application du droit fédéral qui englobe notamment les droits constitutionnels du citoyen (<ref-ruling> consid. 3.1 p. 709; <ref-ruling> consid. 1.2 p. 318) ainsi que les traités internationaux (<ref-ruling> consid. 1b; <ref-ruling> consid. 4b p. 307). Comme il n'est pas lié par les motifs que les parties invoquent, il peut admettre le recours pour d'autres raisons que celles avancées par le recourant ou, au contraire, confirmer la décision attaquée pour d'autres motifs que ceux retenus par l'autorité intimée (art. 114 al. 1 in fine OJ; <ref-ruling> consid. 2 p. 366; <ref-ruling> consid. 3.1 p. 709 et les arrêts cités).
En revanche, lorsque le recours est dirigé, comme en l'occurrence, contre les décisions d'une autorité judiciaire, le Tribunal fédéral est lié par les faits constatés dans les décisions, sauf s'ils sont manifestement inexacts ou incomplets ou s'ils ont été établis au mépris de règles essentielles de procédure (art. 104 lettre b et 105 al. 2 OJ). En outre, le Tribunal fédéral ne peut pas revoir l'opportunité des décisions entreprises, le droit fédéral ne prévoyant pas un tel examen en la matière (art. 104 lettre c ch. 3 OJ; <ref-ruling> consid. 2 p. 366; <ref-ruling> consid. 1 p. 184).
4. L'exercice en Suisse de la profession de médecin est réglée par la loi fédérale du 19 décembre 1877 concernant l'exercice des professions de médecin, de pharmacien et de vétérinaire dans la Confédération suisse (LEPM; RS 811.11), qui a notamment été modifiée par la loi fédérale du 8 octobre 1999 sur l'Accord entre d'une part, la Confédération suisse et, d'autre part, la Communauté européenne et ses Etats membres sur la libre circulation des personnes (RO 2002, 1891, 1914, en vigueur depuis le 1er juin 2002).
4.1 Selon les art. 2b al. 1 et 10 al. 1 LEPM, un diplôme de médecin et un titre de postgrade en médecine étrangers ne sont reconnus en Suisse que si l'équivalence est prévue dans un traité avec l'Etat concerné réglant la reconnaissance mutuelle des diplômes. Reconnus, ils déploient en Suisse les mêmes effets (cf. art. 2a al. 2 et 11 LEPM) que le titre fédéral correspondant (art. 2b al. 2 et 10 al. 2 LEPM).
4.2 La Suisse n'ayant conclu aucun accord bilatéral avec l'Algérie sur la reconnaissance mutuelle des diplômes, le diplôme de médecin du recourant, délivré à Alger, ne peut pas être reconnu pour lui-même en Suisse, puisque la reconnaissance de diplômes étrangers qui ne repose pas sur un traité international de reconnaissance mutuelle n'est plus possible depuis le 1er juin 2002 (Erika Schmidt, Die Medizinalberufe und das Abkommen über die Freizügigkeit der Personen, in: Accords bilatéraux Suisse-UE, Daniel Felder/Christine Kaddous éd., Bâle/Genève/Munich 2001, p. 405 ss, p. 408), ce que le recourant ne conteste pas.
5. Le recourant se prévaut en revanche 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, ou l'Accord; RS 0.142.112.681). Il prétend que la Suisse doit reconnaître son diplôme de médecin délivré à Alger, parce qu'il aurait été reconnu en France ("reconnaissance de la reconnaissance"), ainsi que son titre postgrade de médecine délivré à Paris. La question de savoir si le recourant peut se prévaloir des dispositions de l'Accord relatives à la reconnaissance mutuelle des diplômes peut rester ouverte en l'espèce, car ses recours doivent néanmoins être rejetés pour les motifs suivants.
5.1 Conformément à l'<ref-law>, afin de faciliter aux ressortissants des Etats membres de la Communauté européenne et de la Suisse l'accès aux activités salariées et indépendantes et leur exercice, ainsi que la prestation de services, les parties contractantes ont convenu dans l'annexe III de l'Accord, qui en fait partie intégrante (<ref-law>), d'appliquer entre elles, dans le domaine de la reconnaissance mutuelle des qualifications professionnelles, les actes commu-nautaires auxquels il est fait référence, tels qu'en vigueur au 21 juin 1999, date de la signature de l'Accord et tels que modifiés par la section A de l'annexe ou des règles équivalentes à ceux-ci (art. 1 de l'annexe III ALCP).
Dans la mesure où l'application de l'Accord implique des notions de droit communautaire, seule est en principe prise en compte la jurisprudence pertinente de la Cour de justice des Communautés européennes antérieure au 21 juin 1999 (art. 16 al. 2, 1ère phrase, ALCP). L'art. 16 al. 2, 2e et dernière phrases, ALCP prévoit toutefois que la jurisprudence postérieure à la date de la signature de l'Accord est communiquée à la Suisse et que le Comité mixte en détermine les implications en vue d'assurer le bon fonctionnement de l'Accord à la demande d'une partie contractante. Il en va de même lorsqu'une partie contractante a entamé le processus d'adoption d'un projet de modification de sa législation interne ou dès qu'il y a changement de jurisprudence des instances dont les décisions ne sont pas susceptibles d'un recours juridictionnel de droit interne (<ref-law>). Si une partie désire une révision de l'Accord, elle soumet une proposition à cet effet au Comité mixte. La modification de l'Accord entre en vigueur après l'accomplissement des procédures internes respectives, à l'exception d'une modification des annexes II et III qui sera décidée par le Comité mixte et qui pourra entrer en vigueur aussitôt après cette décision (<ref-law>).
En application des art. 16 al. 2 dernière phrase, 17 et 18 ALCP, l'annexe III ALCP a été modifiée avec effet au 30 avril 2004 par la Décision n° 1/2004 du Comité mixte UE-Suisse portant modification de l'annexe III ALCP pour, selon les termes du Comité, "tenir compte des modifications introduites depuis le 21 juin 1999, essentiellement par les directives 1999/42/CE et 2001/19/CE" (RO 2004, p. 4203; cf. Daniel Felder/Lukas Gresch et al., Sektorielle Abkommen CH-EG von 1999: Erste Erfahrungen, in: Annuaire suisse de droit européen (ASDE), A. Epiney/S. Theuerkauf/F. Rivière éd., Berne 2003, p. 421 ss, p. 433; Erika Schmidt, Revision des Bundesgesetzes betreffend die Freizügigkeit des Medizinalpersonals, in: Bilaterale Verträge Schweiz-EG, Ein Handbuch, D. Thürer/R. H. Weber/R. Zäch éd., Zurich 2002, p. 223 ss, p. 244 ).
5.2 Ces modifications, introduites essentiellement par les directives 1999/42/CE (JO L 201 du 31 juillet 1999, p. 77) et 2001/19/CE (JO L 206 du 31 juillet 2001, p. 1), ont un contenu limité qui est explicité en particulier par le considérant n° 6 à l'appui de la directive 2001/19/CE du Parlement et du Conseil du 14 mai 2001 modifiant notamment la directive 93/16/CEE. Ce considérant expose que, conformément à la jurisprudence de la Cour de justice des Communautés européennes, les Etats membres ne sont pas tenus de reconnaître les diplômes, certificats et autres titres qui ne sanctionnent pas une formation acquise dans l'un des Etats membres de la Communauté (cf. arrêt CJCE du 9 février 1994, Tawil-Albertini, C-154/93, Rec. 1994, p. I-451) mais qu'ils devraient tenir compte de l'expérience professionnelle acquise par l'intéressé dans un autre Etat membre (arrêt CJCE du 9 février 1994, Haim, C-319/92, Rec. 1994, p. I-425) et que, dans ces conditions, il convient de préciser dans les directives sectorielles que la reconnaissance par un Etat membre d'un diplôme, certificat ou autre titre sanctionnant une formation notamment de médecin acquise dans un pays tiers et l'expérience professionnelle acquise par l'intéressé dans un Etat membre constituent des éléments communautaires que les Etats membres devraient examiner (JO L 206 du 31 juillet 2001, p. 2). Le considérant en cause ne fait pas référence à d'autres arrêts de la Cour de justice des Communautés, en particulier à l'arrêt CJCE du 14 septembre 2000, Hocsman (C-238/98, Rec. 2000, p. I-6623), pourtant antérieur à l'adoption, le 14 mai 2001, de dite directive 2001/19/CE et à l'adoption, le 30 avril 2004, de la décision n° 1/2004 du Comité mixte UE-Suisse (RO 2004, p. 4203), ce que confirme la Déclaration de la Commission publiée en annexe à la directive 2001/19/CE (JO L 206 du 31 juillet 2001, p. 51).
Seules les modifications introduites par les directives en cause, qui consacrent une évolution plus limitée que celle qui semble résulter de la jurisprudence plus récente de la Cour de justice des Communautés, sont par conséquent applicables en Suisse, suite à l'adoption de la décision n° 1/2004 du Comité mixte UE-Suisse qui se borne à reprendre les directives en cause.
5.3 Il s'ensuit que la reconnaissance en Suisse d'un diplôme de médecin et d'un titre postgrade en médecine aux fins d'exercer une activité salariée et indépendante ou de fournir une prestation de services est soumise au respect des conditions telles qu'elles résultent des dispositions de la directive 93/16/CEE du Conseil, du 5 avril 1993, visant à faciliter la libre circulation des médecins et la reconnaissance mutuelle de leurs diplômes, certificats et autres titres (ci-après: directive 93/16/CEE; JO n° L 165 du 7.7.1993, p. 1) modifiée par les actes énumérés sous le chiffre 7 de la section A de l'annexe III ALCP (RO 2004 p. 4203, p. 4207 s.) dans sa version en vigueur au 30 avril 2004 (David Hofman, La liberté économique suisse face au droit européen, Berne 2005, p. 411 s. et les références citées; Daniel Felder/Lukas Gresch et al., Sektorielle Abkommen CH-EG von 1999: Erste Erfahrungen, in: Annuaire suisse de droit européen (ASDE), A. Epiney/S. Theuerkauf/F. Rivière éd., Berne 2003, p. 421 ss, p. 433).
6. Selon l'art. 2 de la directive 93/16/CEE, chaque Etat membre reconnaît les diplômes, certificats et autres titres délivrés aux ressortissants des Etats membres par les autres Etats membres conformément aux exigences minimales énoncées par l'article 23 de la directive 93/16/CEE et énumérées à l'annexe A, en leur donnant, en ce qui concerne l'accès aux activités de médecin et l'exercice de celles-ci, le même effet sur son territoire qu'aux diplômes, certificats et autres titres qu'il délivre. Contrairement aux directives du système général (énoncées dans la section A, lettre A de l'annexe III ALCP), la directive 93/16/CEE, qui est une directive dite "sectorielle", instaure un système de reconnaissance automatique des diplômes, certificats et autres titres de médecin dont la liste figure en annexe de la directive (Max Wild, Die Anerkennung von Diplomen, in: Accords bilatéraux Suisse-UE (Commentaires), Daniel Felder/Christine Kaddous éd., Bâle/Genève/Munich/Bruxelles, 2001, p. 383 ss, p. 396 s.).
S'agissant de la reconnaissance des diplômes, certificats et autres titres de médecin spécialiste (diplômes postgrades au sens des art. 7 ss LEPM), l'art. 24 par. 2 de la directive 93/16/CEE exige des Etats membres qu'ils subordonnent la délivrance d'un diplôme, certificat ou autre titre de médecin spécialiste à la possession d'un des diplômes, certificats et autres titres de médecin visés à l'art. 23 de la directive 93/16/CEE.
Enfin, l'art. 42quater de la directive 93/16/CEE, qui est l'expression légale de la jurisprudence de la Cour de justice des Communautés mentionnée dans le considérant n° 6 de la directive 2001/19/CE précitée, impose aux Etats membres d'examiner les diplômes, certificats et autres titres dans le domaine couvert par la directive que l'intéressé a acquis en dehors de l'Union européenne lorsque ces diplômes, certificats ou titres ont été reconnus dans un Etat membre ainsi que la formation et/ou l'expérience professionnelle acquise dans un Etat membre.
Ces dispositions sont directement applicables en Suisse en vertu de l'Accord et de la décision n° 1/2004 du Comité mixte UE-Suisse qui y renvoie (Ulrich Häfelin/Georg Müller, Allgemeines Verwaltungsrecht, 4e éd. Zurich/Bâle/Genève 2002, p. 32, n° 156 et les références citées).
C'est à la lumière de ces considérations qu'il convient d'examiner le diplôme de médecin algérien et le titre postgrade français du recourant.
7. Dans l'arrêt attaqué du 8 février 2005, la Commission fédérale de recours a examiné si le diplôme de médecin du recourant avait été reconnu en France par les autorités françaises compétentes et, le cas échéant, si dite reconnaissance conférait les mêmes droits d'accès à l'exercice de l'activité salariée ou indépendante de médecin qu'un diplôme français de docteur en médecine, ce qu'elle a nié à bon droit. Il est vrai qu'aux termes de l'attestation délivrée le 11 mars 2003 par le Ministère jeunesse, éducation et recherche, Direction de l'enseignement supérieur, produite par le recourant, le diplôme de docteur en médecine obtenu en 1983 en Algérie "peut être reconnu de valeur scientifique équivalente au diplôme français de docteur en médecine". Délivrée par le Ministère en charge de l'éducation et de la recherche et non par le Ministère en charge de la santé, cette reconnaissance revêt une portée strictement académique, par opposition à une reconnaissance professionnelle. En effet, selon cette même attestation du 11 mars 2003, le diplôme algérien en cause "ne permet pas l'inscription à l'Ordre des médecins", mais uniquement "à l'intéressé de s'inscrire au certificat d'études spéciales de radio-éléments artificiels, diplôme obtenu à l'université de Paris XII le 9 octobre 1986". Le Ministère de la santé, Direction de l'hospitalisation et de l'organisation des soins, Sous-direction des professions médicales et des personnels médicaux hospitaliers, seul compétent selon le droit français, a par ailleurs confirmé à l'Office fédéral de la santé publique que l'autorisation d'exercer en France était délivrée par arrêté ministériel émanant du Ministre chargé de la santé, seule cette dernière permettant de s'inscrire au tableau de l'ordre des médecins auquel tous les médecins devaient s'inscrire; il a précisé que l'attestation produite par l'intéressé n'équivalait pas à une autorisation d'exercer en France. Comme le texte clair de l'art. 42quater de la directive 93/16/CEE exige des Etats membres qu'ils examinent les diplômes, certificats et autres titres que l'intéressé a acquis en dehors de l'Union européenne lorsque ces derniers ont été reconnus dans un Etat membre et que le recourant n'a pas produit une attestation délivrée par le Ministère français de la santé valant autorisation d'exercer, la Commission fédérale de recours pouvait à bon droit constater qu'une telle attestation n'existait pas et refuser de reconnaître le diplôme de médecin algérien du recourant, sans qu'une constatation inexacte et incomplète des faits pertinents ni un formalisme excessif ne puissent lui être reprochés. Mal fondé sur ce point, le recours doit être rejeté.
Les arguments que le recourant oppose à cette conclusion sont inopérants. En effet, le recourant méconnaît la distinction entre la reconnaissance d'un diplôme à des fins professionnelles et celle à des fins académiques, la première ayant pour but l'exercice d'une profession dont l'accès est subordonné à une qualification, la seconde visant la poursuite des études et donc la mobilité des étudiants (arrêt 2A.331/2002 du 24 janvier 2003, consid. 4 et les références citées). Il perd également de vue que l'Accord et la directive 93/16/CEE ont littéralement pour but de "faciliter aux ressortissants des Etats membres de la Communauté européenne et de la Suisse l'accès aux activités salariées et indépendantes et leur exercice, ainsi que la prestation de service" (<ref-law> et 5ème considérant à l'appui de la directive 93/16/CEE), ce qui signifie qu'en l'espèce, seule la reconnaissance des diplômes à des fins professionnelles doit être examinée. Au surplus, ce que le recourant aurait pu obtenir comme statut s'il avait été domicilié en France, comme sa soeur, relève d'hypothèses non réalisées qu'il n'y a par conséquent pas lieu d'examiner en l'espèce. Il ne saurait non plus se plaindre d'une violation du droit à l'égalité (art. 8 Cst.), la situation de sa soeur - qui a obtenu l'autorisation d'exercer par arrêté ministériel du Ministère français de la santé - n'étant de ce fait pas comparable à la sienne.
8. Dans l'arrêt attaqué du 3 mars 2005, la Commission fédérale de recours a constaté à bon droit qu'au nombre des exigences conventionnelles de l'art. 24 par. 2 de la directive 93/16/CEE pour la reconnaissance des diplômes, certificats et autres titres postgrade en médecine figurait l'obligation pour les Etats membres de subordonner la délivrance d'un diplôme, certificat ou autre titre de médecin spécialiste à la possession d'un des diplômes, certificats et autres titres de médecin visés à l'art. 23 de la directive 93/16/CEE. Comme le recourant ne pouvait se prévaloir d'un diplôme fédéral de médecin ou reconnu équivalent, ce qui a été confirmé dans le présent arrêt (cf. consid. 6 ci-dessus), l'autorité intimée pouvait, sans violer le droit fédéral, renoncer à l'examen des autres critères relatifs à l'expérience également énoncés dans l'art. 24 par. 2 de la directive 93/16/CEE. Elle ne tombait pas non plus dans un formalisme excessif, puisqu'elle se bornait à tenir compte du fait que ni la situation du recourant en France ni sa situation en Suisse ne satisfaisait à toutes les conditions pour délivrer l'autorisation d'exercer la médecine. Mal fondé sur ce point, le recours doit être rejeté.
Dans ces conditions, la question de savoir si le certificat d'études spéciales relatives aux applications à la médecine des radio-éléments artificiels, qui n'est pas dans la liste de l'annexe C à la directive 93/16/CEE, est équivalent au certificat d'études spéciales en médecine nucléaire, n'a pas à être tranchée en l'espèce. Il en va de même des griefs de violation du droit d'être entendu et de violation du droit à l'égalité liés à cet examen.
Au surplus, le retrait ou le non-renouvellement du droit d'exercer délivré au recourant par le canton de Fribourg ne fait pas l'objet du présent litige, en sorte qu'il n'est pas nécessaire d'examiner les griefs y relatifs de violation du principe de proportionnalité.
9. Les considérants qui précèdent conduisent au rejet des recours de droit administratif. Succombant, le recourant doit supporter un émolument judiciaire (art. 156 al. 1 OJ). II n'a pas droit à des dépens (art. 159 al. 1 OJ).

Par ces motifs, le Tribunal fédéral prononce:
1. Les recours n° 2A.157/2005 et n° 2A.195/2005 sont joints.
2. Les recours de droit administratif sont rejetés.
3. Un émolument judiciaire de 5'000 fr. est mis à la charge du recourant.
4. Le présent arrêt est communiqué en copie au recourant, au Comité directeur des examens fédéraux pour les professions médicales, au Comité de la formation postgrade pour les professions médicales et à la Commission fédérale de recours pour la formation de base et la formation postgrade des professions médicales.
Lausanne, le 13 janvier 2006
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le président: Le greffier: