Starting with which election?
Perhaps either 1988 or 1992? Looking back at prior elections, I know that (or can guess) these major cities last voted Republican in these years:
1. New York City, Boston, St. Louis (MO), St. Paul (MN)-1924 for Coolidge.
2. Detroit-1928 for Hoover.
3. Philadelphia-1932 for Hoover.
4. Chicago, Baltimore, Los Angeles (?), Minneapolis, Cleveland, Pittsburgh, San Francisco-1956 for Eisenhower.
5. Portland (OR)-1960 for Nixon.
6. Atlanta, New Orleans, Durham (NC)-1972 for Nixon.
7. Denver-1980 for Reagan.
8. Austin-1984 for Reagan (?).
These are ones that come to mind currently.
Phoenix likely voted Republican as late as 1988. Dukakis only won one congressional district with area in Phoenix, and much of that included Tucson.