Neither explanation is exactly correct.
Why Is the expansion ratio of the nozzle of the 2nd stage larger than the expansion ratio of the nozzle of the 1st stage of a rocket?
Because it provides higher specific impulse. That is to say, it provides higher thrust for the same mass flow.
The equation for Isp (specific impulse) is:
$$I_{sp}=\frac{F}{\dot{m}g}=\frac{V_e}{g}$$
Here $F$ is thrust, $\dot{m}$ is mass flow, $V_e$ is the gas exit velocity, and $g$ is 9.81 m/s/s.
Notice that the Isp directly scales with exit velocity. How does one produce high exit velocity? With large expansion ratios.
I won't list the equations here as they are nasty and I am lazy. You can see them here. The exit velocity is a function of exit Mach number and exit static temperature. Exit Mach is purely a function of the expansion ratio (and of the ratio of specific heats, but this is usually fixed at around 1.2ish). So engine designers will wish to have large expansion ratios and high chamber temperatures to maximize the exit velocity (and Isp)
Ok, so why don't first stage engines have humungous expansion ratios too? They would if they could.
A high expansion ratio provides the benefits I mentioned, but it also creates a huge pressure ratio, and, as you mentioned, an over expanded nozzle negates many of the benefits. So the limit then becomes the chamber pressure. Engine designers will try to make the chamber pressure as high as possible without prohibitively thick chamber walls. Once they have the design value of chamber pressure, this limits the expansion ratio before the engine becomes too overexpanded.
To summarize: The expansion ratio of upper stage engines is typically higher because it provides higher Isp. And for similar chamber pressures a lower ambient pressure prevents the overexpansion you would see at sea level.
EDIT: In response to the comments, I will address some of the confusion I have created.
The main point is this: the motivation to use large expansion ratios is not necessarily to match ambient pressure. This is a common misconception. Instead the motivation is this: large expansion ratios give the potential for higher Isp at any ambient pressure. Engine designers will employ the largest expansion ratio possible at any altitude. The main limitation is flow separation and pressure drag. If the exit pressure is less than ~a third of the ambient pressure, the flow will separate from the nozzle walls (bad news); and with lower exit pressure, the ambient pressure creates more drag (thanks to the differential pressure), but critically both of these problems are mitigated by high chamber pressure. So the most beautiful sea-level engine would have the same expansion ratio as a vacuum engine but with a massive chamber pressure, such that the exit pressure is at least 0.33 bar. The reason we dont have engines like that is because the extra Isp is not worth the thick walls and ridiculous pumps that would be required. Vacuum engines can have the very high expansion ratios because they don't fear flow separation thanks to the low back pressure.
Basically I want to show you that there are two knobs to turn: chamber pressure AND expansion ratio. This is the nuance your statements are missing. Now I will math this up a bit.
Consider the thrust coefficient (which is directly proportional to Isp):
$$c_f = \frac{F}{P_cA_t}$$
It puts in ratio the total thrust with respect to the product of chamber pressure and throat area. We can compute this coefficient with this equation:
$$c_f = \left[\frac{2\gamma^2}{\gamma-1}\left(\frac{2}{\gamma+1}\right)^{\frac{\gamma+1}{\gamma-1}}\left(1-\left(\frac{P_e}{P_c}\right)^{\frac{\gamma-1}{\gamma}}\right)\right]^{1/2}+\left(\frac{P_e}{P_c}-\frac{P_a}{P_c}\right)\epsilon$$
Here $\gamma$ is the ratio of specific heats, $\frac{P_e}{P_c}$ is the exit to chamber pressure ratio, $P_a$ is the ambient pressure, and $\epsilon$ is the expansion ratio.
Here is a plot of the thrust coefficient as a function of expansion ratio for a variety of chamber pressure to ambient pressure ratios:
First notice that you are correct in your intuitions: The peak thrust coefficient for each condition occurs when the nozzle is perfectly expanded, but notice that as we increase chamber pressure (or decrease ambient pressure) the optimal expansion ratio increases. This is the main point I suppose, large expansion ratios are employed for engines with large chamber to ambient pressure ratios. This occurs with low ambient pressure AND/OR with high chamber pressures, NOT exclusively with low ambient pressure. This is why I said your first statement is not exactly correct.
Regarding your second statement: notice the line marked 1e6 in the plot. Vacuum operation would have an infinite chamber to ambient pressure ratio, and this value of 1e6 is meant to approximate that. See that this line has the highest thrust coefficient for the entire domain; that is to say that any engine will perform best in a vacuum, so the "spreading" of the exhaust gases you describe does not constitute a real detriment. The engine is producing more thrust (and with higher Isp) than it would while perfectly expanded.
