I think I would still pick Shadow. His "death" in Kefka's Tower when he forces Interceptor to leave is a particularly a powerful scene, and I'd hate to sacrifice that.

Shadow, Terra, Celes (to emphasize that there is still hope and kickstart the search for the others), and Setzer because someone needs to fly the god damn airship.

My choices suck. I hate this.