I've managed to unlock 2 classes so far, Gladiator (Battle Master) and Armamentalist (Magic Knight). You get 2 quests in alltrades abby once you can change classes. For gladiator you need to get to super high (100) tension then use dragon slash to kill a slime, you need to do this 3 times and to get 100 tension you need the 16 point monk skill. For magic knight you need to use wizard ward, then the person who used ward has to get the killing blow on a metal slime, this needs to be done twice. While your working on the battle master quest you might as well pick up another quest (also found in alltrades abby). The quest asks you to get to super high (100) tension 5 times, that is it. Once you do this quest you are asked to come back once you have an entertainer at lv 40+ for another quest I would assume. I believe this is part of a chain to later unlock the superstar (don't know it's real name) class.
I just made my warrior into a gladiator, now to start grinding again lol.
Edit: There is another quest you can get in alltrades abby, get a lv 15+ mage to sleep at the inn at the abby and you will get a quest. Once you do that quest they tell you to come back once you have a lv 40+ mage, I'm not sure but that may lead to unlocking the sage class.
Edit 2: Just unlocked paladin, when you get to Gleeba (next place after you get the boat) there's a paladin in the palace that gives you a quest to use whipping boy to take 10 attacks for a party member. I found it easy to do just outside gleeba, there's a monster that has a group breath attack. Not sure on the lv requirement for this, might just be 15+ warrior, my warrior (was a lv 20 gladiator when I found and did this quest) was lv 28 at the time.