The real question is why were there Republican mayors at all? In the last century, exactly four men have been elected Mayor of New York City as a Republican.
It's worth noting that party politics in New York State are a bit odd in that it's one of the few jurisdictions where electoral fusion is still practiced, meaning that a candidate may be endorsed by multiple parties.¹ The first Republican mayor of the last century, Fiorello LaGuardia, ran as such a fusion candidate, and won with “a complex coalition of regular Republicans (mostly middle class German Americans in the boroughs outside Manhattan), a minority of reform-minded Democrats, Socialists, a large proportion of middle-class Jews, and the great majority of Italians.” (https://en.wikipedia.org/wiki/Fiorello_La_Guardia#1933_mayoral_election) He was also helped by the fact that the existing Democratic party apparatus had been damaged by the Tammany Hall scandals of the 1920s. Note that the contemporary ideological sorting of the parties was far from the case now: it's difficult to conceive of 21st-century socialists supporting any Republican candidate for any office today. During his tenure, La Guardia was closely allied with the Democratic president Franklin Roosevelt.
The next Republican mayor, John Lindsay, was a liberal Republican (a category which only became extinct with Reagan’s election in 1980). Before running for mayor, he served in congress with “a liberal voting record increasingly at odds with his own party.” (https://en.wikipedia.org/wiki/John_Lindsay#U.S._Representative) Even so, his initial election was in a three-way race where he ran on the Republican and Liberal Party lines against Democrat Abraham Beame and Conservative William F. Buckley. He lost his re-election primary for the Republican Party, but retained the Liberal Party endorsement and returned to office for a second term. His further political involvement was as a Democrat.
Rudy Giuliani was the next Republican to be elected Mayor and he came to office during a time of high unemployment and crime (although the latter had already begun to decline under his predecessor, David Dinkins). It was his second run for mayor and in both elections (as well as his re-election run) he was on both the Republican and Liberal Party lines but not the Conservative Party which withheld its endorsement. Perceptions of out of control crime doubtless led to Giuliani’s initial success.
Michael Bloomberg, while he ran as a Republican, had been a lifelong Democrat prior to that and ran on the Republican line as much as a strategic means of avoiding the Democratic primary as any declaration of ideology. He eschewed public financing and was able to outspend any of his opponents which likely led to his success while also taking advantage of an endorsement from Giuliani in the midst Giuliani’s renewed popularity after the 9/11 attacks (his approval rating had fallen to 37% in April of 2001).
- In California up until the 1960s, it was not uncommon for candidates to win the general election by running in both the Republican and Democratic primaries. Earl Warren, who was later Chief Justice of the Supreme Court, won the governorship by this method. California effectively ended the process by requiring party identification on the primary ballots and then formally ended it sometime later.