How about this for an idea...what if, when one of your companions is eligible for advancement, you are offered one of two different advancement quests? You may only choose to finish one of the quests, as doing so automatically cancels the one not chosen. Depending on which quest you pursue, that companion gains a different look and different special power. For example: Bonnie Anne...one quest might give her a more powerful, bigger gun, while the other quest might grant her a better/stronger healing power. Each quest would give a slightly different final costume change.
This would increase customization and variety in our final crews.