Where? The entire time I've lived in NYC, in neighborhoods with population density between 30k to 70k people per square mile, I've never, ever, ever had FIOS available to me.
Sure, I've heard about the rare building that has it, but as far as I can tell, it's marketing with just enough actual deployment that we can't call it vaporware.
A while back they told me the fiber had been in the avenues for a long time, but the hinderance was running the fiber from the avenues to the back yard utility poles. Specifically, they needed to get permission and backyard access from every owner on the block to pull cable. Knowing how notoriously difficult it is to get a landlord to do anything in NYC, I imagine this was no easy scheduling task.
You likely lived in an MDU (multiple dwelling unit), i.e. an apartment. FiOS requires the building owner to enter into an agreement with Verizon. It doesn't cost the owner anything, but they have to let Verizon in the door, since Verizon deploys new equipment. Typically it's an MDU ONT (Optical Network Terminal) capable of delivering voice, data, and video over existing infrastructure in the building. In an older building, this typically means that the last 100-1000 feet of your data service is VDSL (over legacy two pair copper) or MoCA (effectively a capable modem over coax).
Which is, like, nobody in new york city. Quit complaining everyone!