Decompressing the palettes is a piece of cake, it's just like the graphics packets. I had to do that for Zeal at Night. I have a spreadsheet that tells all the overworld palette addresses, in fact it should be in the Background insertion tutorial. If not, I'll update it with the overworld palettes. I'll work on the palettes this weekend. I might need to alter a few colors if the recompressed palette is larger than the original palette though, that's the only problem.
Getting the full-size palette Epoch changed should be a quickie, but I'm not sure offhand which palette shift in an overworld is typically used for the little Epoch sprite.
Speaking of the little Epoch, was an actual "overworld Epoch" used for the missile scene or is that an NPC sprite?
If you guys feel crunched by graphics insertion needs, I'd be happy to pitch in after May 12.