George Pataki
Pataki's first job in politics was mayor of his hometown of Peekskill. In 1994 he ran a campaign against Mario Cuomo for Governor of New York. Cuomo was one of the most famous politicians in the country at the time and he was an icon of liberalism in the country. Few people expected Pataki to win, but in a major upset, Pataki won the election.