I cannot see, above, the correct answer to the first part of the question. They all have the second part right.
The first part: Why does shaking the bottle make it fizz when you open it?
The gas is in solution in the closed, unshaken bottle. The solubility of that gas in that liquid at that temperature and that pressure dictates the saturation level of the gas in the liquid. Any more gas than that and it bubbles out, increasing the pressure inside the closed bottle and forcing more gas in solution thus reducing the pressure. An equilibrium is reached.
But why does shaking cause a problem?
Because when you shake it, you slosh the contents around. The liquid flows quickly from one end of the container to the other. As it does so, it flows fast enough to become turbulent. In the turbulence, the curlicues, the intricacies, the eddies and the complex flow there are many locations in the liquid where the local pressure is forced lower than the saturation pressure. This is because any packet of liquid that is accelerating in any direction will leave a low pressure zone in its wake.
When the pressure is forced below the equilibrium level, the gas (given sufficient nucleating seeds) will come of of solution instantly given that the operation is occurring in the bulk and gas bubbles can be created anywhere in 3D.
But when the gas wants to go back into solution it is severely limited by the relatively small surface area of the liquid in the neck of the bottle. There is only a tiny surface available for gas transport through the liquid/air interface. We are severely dissolution rate limited. It can take hours for a shaken can to quiet down. It can be hastened by chilling as more gas can always be dissolved in a cooler liquid.
Assuming you're using degrees Fahrenheit 160F is only (about) 70C so you won't be boiling the water. The increase in pressure will come partly from heating the air in the bottles and partly from the increased vapour pressure of the water.
The pressure of an ideal gas (air is near ideal in this temperature and pressure range) is:
$$ P = \frac{nRT}{V} $$
where $n$ is the amount of gas, $R$ is the gas constant, $T$ is the temperature (in Kelvin) and $V$ is the volume. For any particular bottle the amount of air and the volume is constant, so we can make life simpler by taking the ratio of the pressure after heating to temperature $T$, $P_T$, and the pressure we started off with $P_0$ (the initial pressure, $P_0$, is just atmospheric pressure). So:
$$ \frac{P_T}{P_0} = \frac{T}{T_0} $$
or:
$$ P_T = P_0 \frac{T}{T_0} $$
and we need to add on the vapour pressure of water $P_w(T)$. As the notation suggests the vapour pressure of water changes with temperature. At 70C it's about 30% of atmospheric pressure. Anyhow our equation for total pressure is:
$$ P_{total} = P_0 \frac{T}{T_0} + P_w(T) $$
Note that the volume of the air doesn't appear in this equation, so for the fully immersed bottles (where we can be sure of the air temperature) both bottles will burst at the same temperature.
When you only have the bottles immersed up to the level of the water the temperature of the air isn't well defined because it's heated by the water below it and cooled by the air above it. I would have guessed the air in the bottle with less air would be hotter simply because it sticks out of the water less. I'd expect these bottles to burst at a higher temperature than the fully immersed bottles, but how much higher is hard to say.
In the above I've assumed that you're raising the temperature gradually. Your question implies you're heating the water to 160F then throwing the bottles in. If you're doing that all bets are off because it depends on how quickly the contents of the bottle heat up. You can only do the experiment reproducibly if the put the bottles into cold water and raise the temperature slowly enough for the contents on the bottles to keep up with the temperature rise.
Finally note that this treatment only applies if you keep the temperature below the boiling point of water. Once the water starts to boil the pressure in the bottles will rise extremely rapidly.
Best Answer
I started writing a catchy but long explanation, but since you understand it and want something short for others, let's try this...
If you put too much salt in a glass of water, you saturate the water and end up with salt sitting at the bottom of the glass. If the temperature changes, the amount of salt that can dissolve changes (more for higher temperature, but you can leave that out). (For extra pithy-ness, leave this paragraph out entirely.)
For gases, besides liquid temperature, gas pressure matters. More pressure means more dissolves. When you open the soda and lose the factory-provided pressure, the gas pressure above the soda is suddenly lower, so carbon dioxide starts leaving the soda. It keeps doing this until "enough" CO2 is in the space above the soda. More space means you need more CO2 to fill it up. So, if you crush the bottle to leave less space, less CO2 escapes from the soda, and it stays fizzy.
Of course, this glosses over a lot of usefully clarifying stuff, such as the concepts you mentioned in your post, but it keeps it short. If you can hold their attention long enough, I would throw in a comment about how only the CO2 pressure matters, not the general gas pressure, just so they don't buy those worthless "pump air into your soda bottle" devices.