Theseus's quest takes him from the legendary city of Athens to the island of Crete. Crete is the largest of all the Greek islands and one of largest of the entire Mediterranean. It was once the seat of power of influential Minoan Civilization. It's important to realize that at the time that this legend is set, Crete was way more powerful than Athens. How else would they be able to force the Athenians to send them young people as Minotaur food? So, when Theseus defeats the Minotaur and outsmarts King Minos, it's a classic case of the underdog coming out on top.
The myths of Theseus all take place a super long time ago. Even to the old guys who first wrote down Theseus's story, he was a legendary hero from the distant past. Sometimes the era that Theseus and his fellow heroes lived in is called the Heroic Age. Back in these days, the heroes were the sons of gods and the world was crammed with villains and nasty beasts that really needed slaying.
It's important to think about the fact that even to ancient Greeks, Theseus was an ancient figure. It's pretty likely that the fact that heroes in the stories lived so long ago added to the highly fantastical and exaggerated nature of the tales. If a rumor gets passed around school long enough, it gets totally blown out of proportion, right? Well, it's the same way with myths. Someone tells another person about a cool thing somebody did, then after a thousand years of people retelling the story, it gets totally off the hook.