I've finished writing my custom AVR bootloader. I had to resort to some trickery in order to keep it fitting within 2k but I succeeded.
Here is what it does:
When Dexter board is powered on, bootloader checks a location in the EEPROM to see if last update succeeded. If it did, it immediately boots the Dexter code. So the bootloader is essentially invisible in this scenario.
If the last update did not succeed (or the bootloader has been installed on a fresh microcontroller), the bootloader sends a message on the serial port requesting for the listener on the other end to upload the firmware to it. It will continue to do this indefinitely until it gets the complete firmware program uploaded to it. At this point, it marks in the EEPROM that the firmware programming succeeded and boots the firmware.
This _should_ cover most disaster situations, including the power going out in the middle of a firmware update.
The only situation it doesn't cover is if the firmware itself is defective. The firmware will need to correctly be able to initiate a self-update of itself and if this part of it is buggy, the bootloader has no way of knowing this and will happily continue to boot the firmware. So I also made it so if you hold down the DIAGNOSE button while powering on, the bootloader will initiate the reprogramming sequence no matter what. This is my disaster-recovery option. And if someone does it by accident, it should just reprogram with no harm done.
I think I've covered all the bases.