1) Temperature sensors seldom produce a voltage. If they do, they often cost a lot of money, or they measure temperature very badly.

The cheapest high-precision (0.5°C) sensor I know about are ds18s20 or ds18b20, i.e. Dallas one-wire sensors. Many of them can be connected to a single pin on the processor, but you only get about 1 sample/second because of the slow conversion times in the sensors. Or a ds2439 can be (ab)used which will manage about two temp samples/second and can also produce two voltage or current samples/second.

For lower linearity and precision, a resistive sensor can be used. They are either non-linear, which means that you need a lot of ADC resolution depending on where on the temperature scale your are. Or they may be linear, but with maybe 1-2°C precision and often bigger limitations to the supported temperature range.

A PT-100 or PT-1000 sensor will produce even better readings (and a very large temperature range), but has so small resistance variation for a temperature change that it will take a very explicit circuit to interface such a sensor with a microprocessor.

2) Impedance of input? Yes, that is important. A resistive temperature sensor requires a current to be sent through the sensor. A constant current may be used, and the varying resistance in the sensor will result in different voltages. Or a constant voltage together with a voltage divider can be used. Still a requirement for the current range, but this case will also produce a nonlinear reading. But in both cases, there must be sent a high-enough current through the resistive sensor that the voltage drop will be high enough that it can be read by the ADC. On the other hand - too high current sent through the sensor will produce internal heating in the sensor, affecting the precision.

3) You mention measurements with two digits (0.0 to 5.0V) and then 3 bits. Two decimal digits reaures at least 7 bits (0..127) of resolution. 3 bits gives 8 steps of resolution, i.e. 0V, 0.7V, 1.4V, 2.1V, 2.9V, 3.6V, 4.3V and 5.0V. For a linear sensor, you need at least 8 bits of resolution. Probably 10 bits, since the least significant bit(s) of an ADC can't be trusted. And you also wants a bit or two for any filtering, to avoid a hysterese problem where the value is just on the turn on/off level and very little noise makes two inputs switch places after the sorting, resulting in two relays constantly clicking.

4) If the sensors are not linear, then you need 12 bits or more, and you probably also needs code to normalize the reading before the sort/compare or the sensitivity will vary if all sensors are cold or if all sensors are hot.

5) Multiplexer slow? Yes, it will decrease the maximum number of samples you get from the ADC. But you say you need just a couple of samples/second. If you have an ADC capable of 10kHz sampling rate, then it is obviously fast enough that you can step the multiplexer every 10 ms and get 100 readings/second. This divided by 16 sensors would give 6 readings from each source every second. The limitation on how fast you can switch a multiplexer isn't so much affected by the multiplexer as by the impedance (yet again) of the sensors. How long will it take for the signal to stabilize after you have multiplexed in the next sensor? That affects how soon the ADC can take the next reading.

Few processors have 12 or 16 internal ADC. Normally, the processor has 1 ADC with multiplexed inputs. Each sensor gets one pin on the processor, and the internals of the processor allows a reading immediately after you have switched the internal mux to the next pin. With an external mux, you need a bit of delay. But you do not need to use a 16-to-1 mux. You can use two 8-to-1 or four 4-to-1 or eight 2-to-1. This gives 16-to-2, 16-to-4 or 16-to-8 and allows a higher sampling rate if the sensors are high-impedive and not individually buffered with op-amps.

6) You talk about AND logic to drive your relays. An AND gate is a gate with two or more inputs, with the goal of performing a logic operation - not any buffering, even there are AND-gates with buffered output. If you talk about driving relays, then you should probably use one transistor/output, or possibly a driver chip with many open-collector transistors in the same chip. You also need free-wheel diodes connected over the relay coils to protect the transistors when the voltage to the relay coils are removed. The free-wheel diode have limitations on how many relay deactivations it can handle/second. And the relays have limitations on how many activations/deactivations it can handle in a life-time. If you use MOS-FET transistors instead of bipolar, then you can normally get a smaller transistor with higher current capability, and also often skip the free-wheel diode. But without a free-wheel diode, it will be the transistor itself that will limit the number of deactivations/second, since it will be the transistor that has to "discharge" the stored coil energy.

Conclusion: You still haven't given enough information about your sensors, which makes it hard to:
- figure out how they should be connected to the processor
- figure out how fast they can be read
- figure out how many bits of precision you need for the ADC
- figure out if an external multiplexer is needed
- figure out if normalization need to be done of the read samples

For the outputs, there are also a couple of open issues:
- what voltages and what current for the relays
- min # of activations/deactivations needed / second.
- max # of activations/deactivations allowed / second.

The hardware must be designed for the needed toggle frequency, while the software must be designed to limit to the max frequency supported by the hardware.