For much of the 20th century, New York was slightly (Atlas) redder than the rest of the nation (the exceptions being 1916 and 1948 with New York governors Hughes and Dewey as the Republican nominees). The Democratic tilt in NYC was strongly counterbalanced by upstate and Long Island. That has changed since 1980 with the depopulation in upstate New York plus the increasing liberalization of NYC and the suburbs.
This. But it goes back even further- Cleveland won it in 1884. The Tammany machine has its roots in the 1790s. NYC has some of the most ancestrally Democratic neighborhoods in the country.