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.