The red medal indicates the "boost" or in SDE language, the "premium sailor". Applying that medal to any sailor boosts all of his attributes by 20%. You can actually have hero or elite sailors with two medals: the blue one for hero/elite, plus the red one for the boost.
There are two ways of obtaining those boosts ("red medals"):
1) they can be bought in the item store for 50 olives
2) you gain them during events
You can find them in your ingame shipyard. Go to the red "Item" tab (top right), then to "Sailor Item" and there to "Premium Sailors".