False (but it's still a lot)
Government archives also put the total number of US military fatalities in Vietnam at around 58,000.
The New York City Department of Health provides the statistics for AIDS cases and deaths in NYC from 1980 to ~2014. The second chart in that PDF has the following data in particular:

You can see that in the 1980s there were 19,482 cumulative deaths from AIDS in NYC, and the cumulative total did not exceed 58,000 until 1995. Moreover, this is all AIDS deaths, regardless of sexual orientation, gender, age, or source of infection.
In the following:
- Joseph, Dr. Stephen C.; New York City Department of Health (19 October 1987). AIDS: A Tale of Two Cities: A Report to the Mayor (Memorandum). AIDS, subject files series 80049-5. New York, NY: LaGuardia Community College/CUNY: La Guardia and Wagner Archives, Edward I. Koch Collection, Koch Collection Subject Files.
Data indicates that about 65% of all AIDS cases in New York City involved transmission via homosexual intercourse (about 27% were from IV drug users). To achieve 58318 deaths at 65% of the population would put the total deaths at ~90,000, and the aforementioned statistics show this total was not achieved until 2004. And by that point the disease was no longer affecting the same demographics in the same ways it had during the 80's, so it was probably longer still until 58,000 gay men died of (or at least with) AIDS in NYC.