It appears that this did not originate in New York City.
(Oxford English Dictionary)
bicycle messenger orig. U.S., a courier who uses a bicycle to transport and deliver messages, packages, etc.
1893 N.Y. Times 25 July 3/5 A young man in Evansville, Ind., has started a *bicycle messenger agency, delivering messages and parcels at an average rate of 15 cents a trip.
bike messenger orig. U.S. = *bicycle messenger s.v. BICYCLE n.
1936 Washington Post 31 Jan. 18/3 He saw his first Harvard-Yale football battle as a 14-year-old *bike messenger from the sidelines to a Springfield, Mass., newspaper office.
24 September 1893, Atlanta Constitution, pg. 9:
The First City in the United States to Put the
Bicycle to Practical Use.
A new and novel enterprise, but something that will fill a long felt want and we predict will meet with almost unlimited success has been started by two pushing young men of the city. A bicycle messenger service will open its doors and oil its bicycle tomorrow, at 21 1-2 North Pryor street, ready for the delivery of messages and small parcels. Hardly an hour passes in the store or office of any firm in the city when the urgent demand for the prompt and rapid delivery of a message is not felt. The Bicycle Messenger Service Company purpose to deliver messages in any part of the city or suburbs at a nominal rate and will give prompt and rapid delivery. Expert bicycle riders only will be employed. Parties having messages they want delivered have only to call telephone No. 19 and ask for a messenger boy with his wheel.