Where do I go to find and fight the terrseos?

you can either click on the link in the conversation of the NPC that gives you the task, or you can go to the Battle Colosseum through Games or through Sacred Lands.

, I looked in the Battle Colosseum and didn't see them. Am I just overlooking them?

nope, they're huge and purple, can't miss them. You need to complete another section of the plot to unlock this challenger.

Okay, thanks.

If you aren't sure what step you may have missed out, there's a walkthrough in my siggy :)