I had to do a little quick test:
http://androidarts.com/Amiga/Skyshark.png
I made a 16c pal for the bottom screens (arcade is on top). This is Photoshop's dumb indexing so if you hand pixel the BG blocks you can push more colours into the shading gradients. Even if not the correct hue it usually looks alright. My colour ramps here do double duty, like trees & swamp, grays and ocean. Can't really push saturation too much because then roads might turn blue etc.
Made a little sprite palette for the plane too. With 16c there's hardly any loss.
There are a few instances where you could improve on the original gfx, like, in the swamp at the bridge there's what might be tent cloth stretched into a square... some droops and folds might add some dimension there.