Minotaurs are Heavy Class gladiators. Only two minotaurs are obtainable in the game, Langston and Elexander. Minotaurs are in-accurate are very powerful, especially when paired up with gladiators with abilities such as Sleet and Incapacitate Heavy, which makes the next attack hit guaranteed. Here's how to get the Minotaurs...
To get the first minotaur, Langston, you need to first finish the Mogrel Siege league in Cro Beska. It is possible to get Langston as an amateur when playing as Valens and semi-pro when playing as Ursula. The Mongrel Siege league requires popularity and the Imperia Untamed badge, which you can get in Belfort. As such, it would be a good idea to finish the league when Usus asks you to beat a league in Belfort before moving to Syrna when playing as Ursula.
After finishing the Mongrel Siege league, talk to Cro Beska's shopkeeper. There should be an option to ask about interesting battles. Selecting it will trigger a side-quest for you to come back to Cro Beska in seven days to enter a special league, the Historians League.
Come back in seven days and there should be a new league. You may want to save before entering it because it is possible to get a Satyr named Pan instead of Langston. The league will have one battle against two Satyrs and two Minotaurs, one of them being Langston. There are three citizens that are also in the battle. Normally two of them run into the marshy area of the arena and one tries to fight the Satyrs/Minotaurs. After you beat them, you will either get Langston or Pan. If you do get Pan upon beating the new league, just reset and do it over again (unless you want him)
The second minotaur, Elexander, is available after you've beaten all 4 regions' championship. When you return to Imperia, talk to the Cro Beska shopkeeper again. The Historians League is being held in Syrna (in seven days coincidentally...). To get Elexander, you need to have finished the first Historians League with Langston/Pan.
Go to Syrna in seven days. Again, it may be a good idea to save in case you don't get Elexander. Finish the second Historians League and you will either get a Cyclops, a Satyr, or Elexander. Because you can recruit Cyclopes in the desert and Satyrs in Nordagh, Elexander is typically more desired.