To the ancient Greeks, nothing said strength and skill like a little monster slaying. It seems like it was a requirement that a hero prove himself by slaughtering some monster or another. Perseus beheaded Medusa, Heracles hacked up the Hydra, Odysseus blinded a Cyclopes... the list goes on and on. Even though Theseus defeated a bunch of bad guys in his early adventures, none of his earlier enemies compared to the bull-headed, man-eating Minotaur. So, when Theseus slays the terrible creature, his reputation for strength and skill truly reaches mythic proportions.
When Theseus abandons Princess Ariadne, we see that he's not the squeaky clean hero that we might have thought he was. Even though Ariadne's help was essential for him to complete his quest, he breaks his promise of marriage and ditches her on a random island.
Heroes treating their women badly is actually a pretty common theme in Greek mythology. For example, Jason abandons his wife, Medea, and Heracles plans on abandoning his wife Deinara. In both of these examples, these betrayals end up ruining the hero's life (in the case of Heracles, it actually causes his death).
Some see the suicide of Aegeus, Theseus's father, as a punishment for Theseus's betrayal. Over the years some mythographers cleaned up Theseus's image by saying that love-struck Dionysus demanded that Theseus give up Ariadne. Others said that a storm blew Theseus's ship away. However, the most popular story still seems to be that Theseus was guilty of betrayal.