The first storyline battle you can get them is a pair of Hyrudras in Nelveska Temple. Use Train to recruit one; Invite has a low chance of success. They also appear as random encounters in END in deep dungeon.

Hyrudras are bright orange and the weakest type.

Hydras are black and are the medium type.

Tiamats are gold and are the strongest type. They may in fact be the best recruitable monster in the game. They have multiple attacks, can fly and have insane strength and power.