How do I detect an impending power failure? That sounds really useful!
That depends on how you will be powering the Arduino.
Right now it's being powered from a 12VDC battery. However, the battery can be disconnected manually (there's a big battery disconnect switch). There's no impending warning or shutoff process.
[EDIT: GM got there first, but here goes anyway]
Pass the 12V supply through a diode feeding a large capacitor to ground, and have that feed the voltage regulator that powers the MCU. Put a voltage divider across the capacitor to bring the maximum voltage to below 5V, and feed that to one of the analog inputs. Read that input at regular intervals (every few ms). When the voltage across the capacitor drops below about 10V, assume an impending power failure and write the important data to EEPROM.
Alternatively, feed the output of the voltage divider to the analog comparator, then you can get an interrupt when the voltage is falling.
Unless you have a lot of additional I/O that you haven't mentioned, then any of them will do. The Leonardo and the Uno are inexpensive and easy to use. However, if you are looking for minimum power consumption and you don't need USB connectivity, then you would be better of using a board without the USB-to-serial converter for the final system.
I'm going to guess that the final version will be a custom board, so anything is possible. No additional IO planned, but that depends - I am using a pricey serial LCD display for the prototype. If I can go to a Hitachi HD44780 LCD, I'd need a bunch of IO to drive it , another 4-6 pins for the keypad, and probably one or two LEDs.
The HD44780 text LCD needs 6 pins. A standard 4 x 3 keypad needs 7 pins. Add 7 for the SPI ADCs and that makes 20. Add an analog input for the power fail detection and that makes 21. The atmega328p only has 20 I/O pins if you use an external crystal, however if you use the internal oscillator instead then you have 22.
Another solution for the LCD might be a ST7920-based 128x64 graphic LCD, which needs only 2 pins to drive it.
You might also consider whether a rotary encoder with integral push button might be a suitable input device instead of a keypad. That would only need 3 pins, or you could reduce it to 1 if you use diode multiplexing and shared the pins driving the HD44780.