How can I reduce the size of an AVR ethernet bootloader?
I managed to reduce the size of the bootloader to around 3k. Here is what I did, maybe it helps someone with a similar task:

I removed DHCP and ARP support from the bootloader. I make the assumption that I can always reach the device via UDP broadcast, so I don't need it to obtain an IP address when running the bootloader.

I also did a lot of code tweaking, which helped reduce the size some more. The removal of DHCP/ARP was the biggest chunk, however.