I thought I would use I2C since that leaves the most pins available.
RS-422, RS-485, CANBUS, LINBUS, and Ethernet are likely better choices. It's a question of your expertise, your time, and your money. If you have the knowledge and ability to get I2
C working reliably over about 20 meters then it may be a good choice. Otherwise, pick something else.
They each need a unique I2C address.
Store the address in EEPROM.
I am open to any creative ways to do this. Any ideas?
You don't need anything particularly creative. People have been doing similar things for decades. Store the minimum configuration in EEPROM (the address in your case). Use an appropriate physical layer. The rest is just sitting down and doing it (or stealing it).