Celes is more of a Red Mage, though her magic does tend to focus more on healing and status magic, so Paladin isn't too far. She's a bit more psychically adept than Terra who has much better magic.

Stats don't actually level up in this game without espers, with the exception of HP/MP which do level normally. This game's stats are basically a proto-VII where the whole parties stats are not terribly far from each each other to make it easier to use them for both fighting and magic. Locke, Shadow, and Cyan are the heavy "fighter" characters with poor magic ability which you'll only notice when comparing them to Relm and Stargo, the game's resident "mages". The rest of the cast are largely Red Mage type builds with Esper and equipment customization helping to distinguish them.

Locke is not an atypical thief (he's a treasure hunter), much like Zidane. He's more of a Warrior/Thief hybrid.