A.- L._, ressortissant italien, souffre de séquelles d'une paralysie sensitivo-motrice du membre inférieur droit depuis l'âge de trois ans. Depuis le 17 janvier 1982, il réside en Suisse où il a travaillé, en qualité de peintre en bâtiment, de un à plusieurs mois par année, jusqu'en mars 1990 (sous réserve de l'année 1984).
Il a déposé une demande de prestations de l'assurance-invalidité tendant au reclassement dans une nouvelle profession (le 18 décembre 1997) et à l'octroi d'une (nouvelle) orthèse tibiale (le 28 janvier 1998).
Dans un rapport du 22 janvier 1998, se référant à l'avis de son confrère C._, professeur associé à la Faculté de médecine X._, spécialiste en neurologie, le docteur B._, médecin traitant, a diagnostiqué une scoliose avec bascule du bassin et raccourcissement du MID; il a fixé l'incapacité de travail de L._ à 100 % dans son activité de peintre en bâtiment (sans indication de date).
Le docteur O._, spécialiste en chirurgie orthopédique, a diagnostiqué des séquelles de paralysie du membre inférieur droit (MDI) avec lombo-sciatalgies droites sur raccourcissement du MDI et fixé l'incapacité de travail de L._ à 100 %, depuis 1991 (rapport du 6 juillet 1998). Selon ce médecin, le prénommé avait pu travailler comme peintre en bâtiment, du fait que les lombalgies à leur début étaient bien tolérées.
Par décision du 19 avril 1999, l'Office de l'assurance-invalidité pour le canton de Vaud (ci-après : l'office AI) a rejeté la demande de prestations, au motif que l'invalidité de l'assuré remontait à une date antérieure à son entrée en Suisse.
B.- L._ a recouru contre cette décision devant le Tribunal des assurances du canton de Vaud, en concluant à l'octroi de mesures de reclassement.
Par jugement du 16 avril 2000, l'autorité cantonale a admis le recours, annulé la décision entreprise et renvoyé la cause à l'office AI pour qu'il complète l'instruction au sens des considérants et qu'il rende une nouvelle décision.
C.- L'office AI interjette recours de droit administratif contre ce jugement, dont il requiert l'annulation.
L._ conclut au rejet du recours. Dans le cadre de ses observations du 20 octobre 2000, l'Office fédéral des assurances sociales propose de trancher la question litigieuse au regard du droit à venir.

Considérant en droit :
1.- Même si elle ne met pas fin à la procédure, une décision de renvoi qui invite l'administration à statuer à nouveau selon des instructions impératives, est une décision autonome, susceptible en tant que telle d'être attaquée par la voie du recours de droit administratif, et non une simple décision incidente (<ref-ruling> consid. 1a, 117 V 241 consid. 1; VSI 2001 p. 121 consid. 1). Il y a donc lieu d'entrer en matière sur le recours.
2.- En instance fédérale, l'objet du jugement attaqué est l'annulation de la décision du 19 avril 1999 et le renvoi du dossier à l'office recourant pour qu'il complète l'instruction au sens des considérants (cf. <ref-ruling> consid. 2c, 121 III 477 consid. 4, 115 V 418 consid. 3b/aa, 113 V 159; VSI 2001 p. 121 consid. 1) et, implicitement, pour qu'il rende une nouvelle décision sur le droit éventuel de l'intimé à des mesures de reclassement.
3.- a) Selon l'art. 8 let. c de la Convention relative à la sécurité sociale du 14 décembre 1962 entre la Suisse et l'Italie - dans sa version modifiée par le deuxième Avenant du 2 avril 1980 à la convention - les ressortissants italiens peuvent prétendre les mesures de réadaptation aussi longtemps qu'ils conservent leur résidence en Suisse et si, immédiatement avant le moment où est survenue l'invalidité, ils ont payé des cotisations à l'assurance suisse pendant une année au moins.
Cette règle conventionnelle directement applicable (cf. dans ce sens <ref-ruling> et 237 consid. 3c, 119 V 177 s.v. consid. 4b) impose des obligations et confère des droits non seulement aux autorités mais aussi aux particuliers. Elle prévaut sur les dispositions de la LAI relatives au droit aux prestations.
b) Aux termes de l'<ref-law> al. 1 - dans sa teneur applicable en l'espèce, en vigueur jusqu'au 31 décembre 2000 - les ressortissants suisses, les étrangers et les apatrides ont droit aux prestations de l'assurance-invalidité, s'ils sont assurés lors de la survenance de l'invalidité.
4.- a) Se fondant notamment sur le rapport du docteur O._, les premiers juges ont considéré que la condition d'assurance requise par les <ref-law> et 8 let. c de la convention italo-suisse de sécurité sociale était remplie, dès lors que c'est en 1991 que l'intimé a eu besoin de mesures de reclassement.
L'office recourant conteste cette appréciation. Selon lui, l'intimé est atteint d'une poliomyélite aiguë depuis son enfance, ayant occasionné une paralysie des muscles du MDI qui serait incompatible avec son activité de peintre en bâtiment. Le fait que l'intimé n'a travaillé qu'à temps partiel de 1982 à 1990 témoignerait en faveur de cette thèse. L'office recourant fait dès lors valoir que l'invalidité de l'intimé est survenue avant son entrée en Suisse en 1982 et que les mesures de reclassement auraient été nécessaires également avant cette date.
b) Selon l'art. al. 2 LAI, l'invalidité est réputée survenue dès qu'elle est, par sa nature et sa gravité, propre à ouvrir droit aux prestations entrant en considération (<ref-ruling> consid. 2b, 118 V 82 consid. 3a et les références; VSI 1998 p. 209 consid. 3a).
Une seule atteinte à la santé peut entraîner plusieurs cas d'assurance successifs : la survenance de l'invalidité doit être déterminée séparément pour chaque genre de prestation qui entre en ligne de compte (<ref-ruling> consid. 1b).
Selon la jurisprudence (arrêts non publiés M. du 11 mai 1999, I 301/98, G. du 11 novembre 1987, I 192/87), la survenance de l'invalidité en ce qui concerne une éventuelle mesure de reclassement se situe au plus tôt au moment auquel l'atteinte à la santé est devenue suffisamment importante pour que l'on doive s'attendre à ce que, dans un avenir proche, l'activité exercée ne puisse plus être raisonnablement exigée de l'assuré.
c) Il ressort du dossier médical que l'atteinte à la santé de l'intimé consiste en une scoliose et des séquelles de paralysie du MDI avec lombo-sciatalgies et qu'elle a provoqué, dès le début de l'année 1990 (dernière période de travail selon les extraits de comptes individuels), en raison de l'aggravation des douleurs lombalgiques, l'interruption de travail. Le docteur O._ a ainsi fixé le début de l'incapacité de travail à l'année 1991. On doit dès lors admettre, conformément à la jurisprudence précitée, que c'est en 1990, au plus tôt, et en 1991, au plus tard, que l'atteinte à la santé de l'intimé est devenue suffisamment importante pour qu'il ne puisse plus exercer son activité de peintre en bâtiment.
d) Dans ce contexte, non documentés et en contradiction avec les constatations médicales, les moyens de l'office recourant doivent être rejetés. Contrairement à ce qu'il soutient, aucun élément du dossier ne permet d'affirmer que les interruptions de travail comme peintre, mises en évidence par les extraits des comptes individuels, sont imputables à l'état pathologique préexistant ou que l'intimé ne travaillait pas à plein rendement lorsqu'il était actif professionnellement. Par ailleurs, on ne voit pas de motifs de s'écarter de l'avis, en particulier, du docteur O._, selon lequel le début de l'incapacité de travail doit être fixé à une date correspondant à l'aggravation des douleurs lombalgiques. A tout le moins, et sur la base des certificats médicaux, on ne saurait considérer que l'atteinte à la santé était, avant 1982 déjà, suffisamment importante pour que l'activité de peintre ne puisse plus être exigée raisonnablement de l'assuré alors même qu'il l'a exercée jusqu'en 1990.
Il s'ensuit que la condition d'assurance requise par les art. 8 let. c de la convention italo-suisse de sécurité sociale et 6 al. 1 LAI était remplie en ce qui concerne une éventuelle mesure de reclassement.
5.- Cela étant, on doit admettre, avec les premiers juges, que le dossier ne contient pas les éléments suffisants pour statuer en connaissance de cause sur le droit de l'intimé à une éventuelle mesure de reclassement, au regard, notamment des conditions posées par la jurisprudence (<ref-ruling> sv. consid. 2b; VSI 2000 p. 64 consid. 1).
Un complément d'instruction s'impose. Dans ces circonstances, l'autorité cantonale était fondée à renvoyer la cause à l'office recourant pour complément d'instruction et nouvelle décision (voir aussi RAMA 1993 no U 170 p. 136, 1989 no K 809 p. 206).
6.- L'intimé, qui obtient gain de cause, est représenté par la Fédération suisse pour l'intégration des handicapés (FSIH) et a droit à une indemnité de dépens à la charge de l'office recourant (<ref-ruling> consid. 2).

Par ces motifs, le Tribunal fédéral des assurances
prononce :
I. Le recours est rejeté.
II. Il n'est pas perçu de frais de justice.
III. L'office recourant versera à l'intimé la somme de 800 fr. (y compris la taxe à la valeur ajoutée) à titre de dépens pour l'instance fédérale.
IV. Le présent arrêt sera communiqué aux parties, au Tribunal des assurances du canton de Vaud, à la Caisse cantonale vaudoise de compensation, et à l'Office
fédéral des assurances sociales.
Lucerne, le 10 avril 2001
Au nom du
Tribunal fédéral des assurances
Le Président de la IIe Chambre :
La Greffière :