I'll provide multiple reasons, all of which work together in undeterminable proportions, rather than just one, to provide a total picture of the context for these electoral decisions, which at first blush do seem counterintuitive.
Local Government In The U.S. Isn't Very Partisan Relative To State and Federal Government Offices
In an executive branch elected office where implementing the law rather than making broad legislative decisions is at issue, as in the case of New York City's Mayor, the individual who is running for that office matters more than their nominal political affiliation.
The saying goes that there is no Republican or Democratic way to fix a pothole. Local government is mostly seen as involving technocratic issues where competence is an issue, even though that is not entirely the case.
In most U.S. cities, city offices aren't even partisan, i.e. candidates don't run under the banner of a political party.
Even where local government offices are partisan, there is very little coordination between federal and state partisan elected officials on one hand, and local government partisan elected officials on the other, unlike in Europe, where there is typically tight coordination between local government representatives of a political party, and the national party's agenda.
There is no detailed local government level agenda of specific policies being pushed for nationwide at this level in either the Democratic Party or the Republican party in the U.S.
Executive Branch Elections Are Ultimately For An Individual And Not A Political Party And U.S. Political Parties Are Extremely Weak Anyway
In the United States, political parties in the U.S. are so weak that the party leadership has almost no control over who runs under the political party's banner, if primary voters back a candidate.
Political parties in the U.S. have no almost control, either formally, or through the informal political culture, over how politicians elected to public office act once elected and the influence of a political party is particularly weak in the cases of executive branch elected officials like mayors and governors.
U.S. political parties were dramatically weakened, to be among the weakest in formal powers in the world, in late 19th century and early 20th century "progressive era" reforms seeking to weaken corruption and "machine politics." Later campaign finance reform movements further undermined the economic power of political parties in the U.S.
As a result, the political party affiliation of candidates, especially for executive branch offices upon whom the legislative party cannot impose effective discipline, doesn't matter much.
You see the same thing at the state level in statewide executive branch elected officials. Deep blue Massachusetts elected Republican Governor Romney. Deep red Montana has elected Democrats to statewide office.
Ultimately, voters are just choosing between two individuals in a race for an executive branch office and if their own preferred party's candidate is unimpressive or tainted, and a member of another political party's candidate looks promising and seems to lack the flaws one worries about for other offices, that person can be and often is elected.
Split Control Limits An Elected Official's Impact And Can Be Good
Also, the fact that Democratic leaning cities have Democratic party controlled city councils, and that Democratic leaning states have Democratic party controlled state legislatures (and visa versa) means that the amount of "damage" that an opposite political party executive branch official can do is very limited and is subject to intense and daily oversight from the legislative branch.
Party splitting at a level of government is also a way for voters to check the more ideological wings of their own parties from getting too extreme.
Incumbency Effects
Another factor that can push an atypical political party choice for an elected office is that it is almost impossible to oust a mediocre incumbent in a political party primary due to political norms and traditions, so often the only alternative to a bad incumbent is a member of another political party.
Likewise, even if voters wouldn't normally vote for a member of a political party, if an incumbent has done a satisfactory job, the incumbent will usually be re-elected. Political science studies show that people tend to vote on incumbent candidacies as a referendum on the results that the incumbent has produced and the incumbent's performance, rather than by evaluating the incumbent and the opponent with an open mind as equal choices to consider.
Political Party Identification Doesn't Mean The Same Thing Everywhere
Finally, it is worth recalling that the ideologies and character of members of a political party is not uniform nationally, although the major political parties in the U.S. have "purified" somewhat in recent years on ideological lines.
In a place like New York State, Republicans have historically been far from the national republican stereotype (particularly on some "socially liberal" and environmental issues) in both policy and image, while ambitious conservatives has tried to shoehorn their key agenda items into the dominant party (producing "neo-liberals" who are moderate in economic and foreign affairs, and socially liberal).
Rudy Guillani and Michael Bloomberg were both conservatives and Republicans, but neither ran for Mayor on a truly "far right" platform, and both presented urban and cosmopolitan rich guy images to the public, rather than trying to be sympatico with working class Evangelical Christian voters as Donald Trump, another New York City billionaire, did in his national run for President.
In contrast, in Red States, Democrats tend to stake out some conservative stances, as they must to get elected, and a conservative image, while ambitious political figures who are moderate or liberal leaning try to find a spot in the Republican Party where they can be elected.
For example, I lived in conservative Grand Junction, Colorado for a while where I worked on the campaign of an ambitious young Democrat running for the state house of representatives on his campaign (he was crushed). A few years later, he changed parties and ran for the executive branch office of District Attorney as a Republican, where many issues he ran on for the state house didn't serve as baggage with Republican voters since the DA's office didn't deal with those issues, and won. Examples of such strategies are common in states, and in areas within states, where one political party or another is dominant.