Optiboot is about the smallest bootloader available.
But, there is a much more powerful (with inbuilt console for hardware testing, RAM and Flash contents checking, etc) bootloader with a more developed and robust stk500v2 communications protocol between avrdude and the AVR bootloader.
I've used it on the ATmega2560 and on the ATmega1284p. It works for both 3 byte and 2 byte program counter MCU.
I have a STK500v2 Bootloader version on Sourceforge.
This bootloader is based the Peter Fleury STK500v2 bootloader, updated by Mark Sproul. I've made edits to have it supporting with the Goldilocks (an ATmega1284p) board.
The key feature is to use the STK500v2 protocol for uploading the Flash image to the Arduino. This protocol is more robust and gives better error capabilities than the avr109 protocol. As an aside the avr109 protocol is called "Arduino" in the Arduino world, because it toggles DTR (to reset the board and automatically enter the bootloader), and the STK500v2 protocol is called "Wiring" in the Arduino world, because of the same reason.
The Fleury/Sproul STK500v2 bootloader is designed to work with the ATmega2560 which has a 3 byte program register, because of the larger Flash size. But, it also supports normal 2 byte boards (everything else really).
For boards with plenty of Flash (like Goldilocks 1284p), there is a hardware monitor that can be used to query Flash, SRAM and hardware; you can check connections without additional code, and check the actual contents of Flash and EEPROM. Because the 1284p supports 2 USART, I added the ability to have debugging on USART1, so that the upload process via USART0 isn't disturbed.