NYC electrical code

The GFI can be 15A, but it must be on a 20A circuit.

I do not know what is specifically required within the five boroughs of NYC.

However, the NEC requires that there be two 20 amp circuits for the small appliance receptacles in a kitchen. And yes, they should be GFCI protected outlets.