I'm just pulling all this out of my head at the moment, it may or may not work, but here's my idea.
The simple way to make a circuit that can be battery powered or plugged in is to put in a diode. The anode connects to the top battery +V terminal. The cathode connects to a DC wall transformer's +V and the rest of the circuit. The wall wart must be at least .8v higher than the maximum you expect from the battery. This way, when the unit is not plugged in, the batteries conduct through the diode and power the circuit. When it is plugged in, the diode stops conducting, since the anode is now at a higher voltage than the anode, so the batteries stop. If it's plugged in, and you suddenly unplug it from the wall, the battery switchover is instant.
I don't think something this simple would work with two same voltage batteries, and have a lower one switch to a higher one. What you could try is to make a small circuit with a zener diode or some other device that produces a stable voltage output regardless of small input changes. Use this as a base for a voltage comparator. For the voltage comp's test input, connect the main battery terminal straight to it. When it is no longer able to keep the diodes biased, the comparator fails, which will trigger a relay to switch to the backup battery.