Programmable gain instrumentation amplifier with R-2R ladder and analog multiplexer

Your circuit doesn't make much sense: for two of the inputs you use an amplifier as attenuator, for a third one a x1 amplifier. Only for the R4 position you use it as a x10 amplifier.
Besides, why did you choose such low resistance values? For the 10 Ω most analog switches will have a significant on-resistance, even if they're as low as 1Ω: that's 10 %. If you scale all resistances up by a factor 100 you'll have the same attenuation/amplification.

Analog switches with low on-resistances exist, but their inputs are limited to the power supply, and then 40 V is an issue.

You say you want solid-state, but a relay may be the better performer, especially a reed relay. Low on-resistance of 150 - 200 mΩ, low off-capacitance, in the order of 1 pF, capable of switching high voltages and high frequencies.

Then your configuration. I would replace R2 and R3 by a resistor divider with taps at :10 and :100. Your third relay (for :1) comes at the top of the divider, from where you also go to the x10 amplifier, whose output goes to the last relay. You'll want to protect the input of that amplifier against overvoltage with low-capacitance clamping diodes.

1. You can use any amplifier you like. You will get better performance if you use a modern $5 dual op-amp than a 2-cent/amplifier LM324. Sub-zero means nothing to me. If you want to the amplifier to have guaranteed characteristics below 0°C, then you should buy one that is guaranteed for that temperature range. Below -55°C you may have to qualify them yourselves. For temperatures down to -20°C it's unlikely that anything untoward will occur other than possibly slightly worse performance for a chip guaranteed over the commercial temperature range. A single 5V supply will impose significant limitations on the input common mode voltage. You can add pullup resistors to the output of an LM324 to get a bit more range (you probably do not want to do this on the output amplifier). Note that the left two amplifiers can saturate at either rail, so even if the output should be within range that doesn't mean that the amplifier will work properly. I presume your common mode input voltage will be close to 2.5V so this may not be a problem. LM158 and LM124 ancient designs are particularly crappy amplifiers for low level DC- large offset voltage and large offset drift with temperature.

2. See above. Offset voltage, offset voltage drift. Probably useful range of input. Closed loop gain accuracy will likely be lower too, because of op-amp gain.

3. If you could use an analog switch with your micro to auto-zero the amplifier you could improve performance. A SPDT switch is sufficient (eg. 1/2 74HC4066). Just transfer one input to be shorted to the other at ~2.5V and measure the amplified offset voltage. Average over many measurements and subtract from the measured signal.