I don't actually need to reprogram the chips remotely, I just want it to be easy to do the initial programming.
If you can do one over the serial link you can do the other. If this is for a project that may require field upgrades this will be a very good feature to implement properly.
It sounds like I will be able to upload the sketch through the max485 as long as I manually reset the atmega first. Is that correct?
It will be a bit like the current Arduino setup when the program stops the bootloader from executing. IE you have to time pressing the reset button just right, so as long as the board and the PC are next to each other I think it should work (you'll need a USB to RS-485 adapter for the PC). If this is just for the initial programming and not in the field it should be OK.
Another option is to do ISP programming using the SPI pins if they aren't already in use.
Rob