On a concept level, magitek knights (which is basically what Tina/Terra and Celes are) are rather close to Red Mages.
The reason Paladins have cover is because of cecil who made it a staple ability for PLDs in FFIV. Runic and Cover have nothing to do with one another. That's not even going into how one belongs to a knight and the other belongs to a magic swordsman. PLD is of the former, RDM is of the latter (refresh-whoring notwithstanding).