Faits: Faits: A. M._, ressortissant portugais, né en 1952, a travaillé en Suisse dès le mois de mars 1993 en tant qu'aide-jardinier saisonnier. Victime d'un accident le 22 décembre 1994, il a subi une lésion de la coiffe des rotateurs de l'épaule droite et a été incapable de travailler jusqu'au 25 juin 1995. Il a ensuite repris son activité à 50 % jusqu'au 30 novembre 1995, date à laquelle il a été licencié. Le 17 octobre 1995, M._ a déposé une demande de prestations auprès de l'Office de l'assurance-invalidité pour le canton de Vaud (ci-après : l'OAI) afin d'obtenir des mesures de reclassement dans une nouvelle profession. Ensuite d'une chute survenue le 14 juillet 1996, il a été opéré au mois de mars 1997 pour une lésion du ligament croisé du genou droit. L'OAI a recueilli des renseignements médicaux et versé au dossier deux expertises mises en oeuvre par l'assureur-accidents de l'intéressé. Dans la première expertise (rapport du 15 janvier 1998), le docteur A._, spécialiste en chirurgie orthopédique et traumatologie, a conclu à une capacité résiduelle de travail de 75 % dans une occupation lourde (maçon) et à une capacité de travail de 100 % dans un métier adapté (chauffeur de taxi, surveillant, magasinier ou encore aide-jardinier, mais seulement dans des occupations légères). Dans une expertise du 1er juillet 1999, les médecins de l'unité d'orthopédie et de chirurgie de l'appareil moteur de l'hôpital H._ ont constaté une incapacité de travail entière dans l'activité d'aide-jardinier, et une capacité de travail de 100 % dans une profession sédentaire ne nécessitant pas l'utilisation de l'épaule droite en élévation. En outre, M._ a effectué un stage d'évaluation du 7 au 25 juillet 1997 au centre d'observation professionnelle de l'assurance-invalidité X._. Il ressort notamment du rapport final que l'intéressé était peu limité dans ses mouvements, mais que le port de charges devait être évité. De son côté, l'assuré a produit un rapport d'expertise du docteur B._, spécialiste en chirurgie orthopédique, du 2 juillet 1998, qui faisait état d'une capacité résiduelle de travail de 0 à 25 % dans la profession de maçon. Par décision du 1er mars 2000, l'OAI a rejeté la demande de prestations, motif pris que le taux d'invalidité de M._ était de 9,1 %. M._ a recouru contre cette décision devant le Tribunal des assurances du canton de Vaud. Il a conclu à son annulation et à l'octroi d'une rente entière d'invalidité et, subsidiairement, à la mise en oeuvre d'une nouvelle expertise médicale. En cours de procédure, M._ a produit une expertise du 8 janvier 2001 du docteur C._, (Portugal), spécialiste en chirurgie orthopédique. Celui-ci a repris le diagnostic établi précédemment, mais a conclu à une "incapacité permanente partielle" (IPP) de 61,2 %. Par jugement du 17 décembre 2001, le Tribunal des assurances du canton de Vaud a décliné sa compétence en raison du domicile au Portugal de M._ et a renvoyé la cause à la Commission fédérale de recours en matière d'assurance-vieillesse, survivants et invalidité pour les personnes résidant à l'étranger (ci-après: la commission de recours) comme objet de sa compétence. Par jugement du 19 février 2002, la commission de recours a annulé la décision de l'OAI et transmis le dossier pour nouvelle décision à l'autorité compétente, à savoir l'Office de l'assurance-invalidité pour les assurés résidant à l'étranger (ci-après: l'OAIE). Par jugement du 19 février 2002, la commission de recours a annulé la décision de l'OAI et transmis le dossier pour nouvelle décision à l'autorité compétente, à savoir l'Office de l'assurance-invalidité pour les assurés résidant à l'étranger (ci-après: l'OAIE). B. Le 14 mai 2002, l'OAIE a rendu une décision par laquelle il a rejeté la demande de prestations de M._. Il a conclu que sa capacité de travail était entière dans une activité adaptée et, compte tenu de la comparaison des revenus déterminants, qu'il ne subissait qu'une diminution de sa capacité de gain de 9,1 %, comme l'avait établi l'OAI. B. Le 14 mai 2002, l'OAIE a rendu une décision par laquelle il a rejeté la demande de prestations de M._. Il a conclu que sa capacité de travail était entière dans une activité adaptée et, compte tenu de la comparaison des revenus déterminants, qu'il ne subissait qu'une diminution de sa capacité de gain de 9,1 %, comme l'avait établi l'OAI. C. Saisie d'un recours de M._, la commission de recours l'a rejeté par jugement du 24 février 2003. C. Saisie d'un recours de M._, la commission de recours l'a rejeté par jugement du 24 février 2003. D. M._ interjette un recours de droit administratif en concluant, sous suite de dépens, principalement à la réforme du jugement attaqué en ce sens qu'une rente entière d'invalidité lui soit allouée dès le mois de novembre 1996, et subsidiairement à l'annulation de la décision attaquée et au renvoi de la cause pour complément d'instruction. L'OAIE conclut au rejet du recours en se référant à un préavis de l'OAI. L'Office fédéral des assurances sociales a renoncé à se déterminer.