Banyan:
You are by no means the first one to get confused about the difference between textbook discussions of "galvanic" or "voltaic" cells and what happens in the real world. Let's start by noting that the terms "positive" and "negative" can be confusing because the anode is positive in electrolytic cells and negative in a galvanic/voltaic cell. From the perspective of a chemist, it seems easier to remember that "anions" flow to the "anode" and "cations" flow to the "cathode." This seems reasonable inasmuch as the four terms were introduced by William Whewill in the 1830's. Why would cations flow to the cathode in a galvanic/voltaic cell? Because reduction always occurs at the cathode. And, oxidation always occurs at the anode. So if we are looking at a prototypical voltaic cell based on the Cu/Ag+ half cells, the positively charged Ag+ ions flow toward the cathode, where they are reduced to silver metal. This is often demonstrated by putting a piece of copper wire into a solution of the Ag+ ion. One sees silver "whiskers" grow on the copper metal surface, while the solution turns a faint blue color characteristic of the formation of an aqueous solution of Cu2+ ions.
It is therefore tempting to consider the cathode as being "negative" because it is the source of the electrons that reduce Ag+ ions (or "cations") to silver metal. Whereas this demonstration can be used to help students (of all ages!) remember that the processes of oxidation and reduction, it doesn't help us understand voltaic cells because there is no voltage! To get the cell to do work, we have to separate the oxidation and reduction half-reactions. So let's use another classic example, Cu2+ being reduced at the cathode to copper metal in one half-reaction and zinc metal being oxidized to form zinc metal in another half-reaction that occurs at the anode. The Cu2+ cations flow to the cathode, where they are reduced, while Zn metal is being oxidized at the anode to form Zn2+ ions. Where are the anions that are supposed to flow to the anode? To complete the circuit, positively charged cations in the salt bridge flow into the half-cell around the cathode to balance the charge that would develop as Cu2+ ions are reduced. Negatively charged anions flow out of the salt bridge into the solution around the anode to balance the charge that develops as Zn2+ ions are released into the solution.
We are now ready to look at your examples. But let's digress for a moment to think about the repaid of the Statue of Liberty. Which part needed to be replaced, the copper on the outside of the statue or the iron bars that formed the skeleton? (It was the iron skeleton that had to be replaced because of an electrochemical reaction in which the oxidation of iron metal is facilitated by contacting with the copper metal on the outside of the statue. The phenomenon being demonstrated her is "overvoltage."
One mistake in your argument about what should be expected can be found in the phrase: "stainless steel and copper are both rather cathodic." The reaction that would occur if iron nails were used to hang a copper-metal roof is not between the two metals; oxygen binding to the surface of the copper metal is available to oxidize the iron, which therefore loses its structural integrity. Furthermore, it is a mistake to think in terms of both metals as "cathodic." The fundamental question is always the relative activity of the two metals. E.g., iron is more active than copper. Aluminum is more active than either of these two.
So we now have an interesting question about the relative activity of iron and aluminum. There is a considerable difference in the standard-state reduction potentials of Al3+ and Fe2+ or Fe3+ ions. The relative activity is often demonstrated by putting a mixture of Fe2O3 and powdered Al metal in a porcelain crucible supported on a ring stand above a large sand box that is, itself, above an even larger piece of asbestos, with the whole apparatus surrounded by a large safety shield. A small amount of BaO2 is placed on top of the "thermite" mixture and ignited by adding a few drops of glycerin. Localized heating as a result of the barium peroxide oxidation of the glycerin ignites the "thermite" mixture, large flames shoot out of the top of the porcelain cup, and red-hot molten iron metal drops through a hole in the bottom of the cup into the sand bath. In the course of this reaction the aluminum metal is oxidized to Al3+ ions, while the Fe2O3 is reduced to red-hot iron. Would one predict that this reaction should occur based on the relative "activity" of Fe and Al metals. Yes! Does the reaction occur at room temperature? No! I have a large box of the thermite mixture in our lecture demonstration facility that is at least 50 years old, with no sign of reaction. Why not? Because thermodynamics (e.g., predictions based on electrochemical potentials) can only tell us what should happen; kinetics tells us whether it will happen (under a particular set of conditions).
We now have a fascinating question: If aluminum is so much more "active" than iron, why don't airplanes burst into flame? Why can we wrap a turkey in aluminum foil and cook it for hours without the oven bursting into flame? Because aluminum is so reactive than a fairly even coating of substances such as Al2O3 forms on the surface, which impedes further reaction. If you are careful, you can demonstrate this by adding small(!!!) pieces of aluminum foil into a beaker that contains liquid bromine. It takes awhile before the bromine cleans the surface of the metal, but, when it does, one sees bright flashes of light and bromine vapor boiling out of the beaker. (Please don't do this unless you fully understand how to do this demonstration safely.)
We need to invoke one last argument to differentiate between what you encounter in chemistry classes and the real world. The electrochemical half-cell potentials that can be found in textbooks are "standard-state" half-cell potentials. In other words, the ideal behavior of a half-cell in which all solutions are 1 M and all pressures at 1 bar. I.e., conditions unlike those encountered in the real world. Furthermore, we need to remember that I have based this discussion on the behavior of the iron in steel, not stainless steel in which is an alloy with chromium.
