What is the Christian definition of "The Messiah"? Christianity is the religion of people who consider Jesus to be "The Messiah".

But what is the Christian definition of "The Messiah"?

Since Christian theology is based on the notion of "The Messiah's" first coming, what are the criteria that one has to fulfill during their "first coming" in order to be regarded as "The Messiah"?
I think there is an assumption behind your question that is not quite right, regarding the Christian conception of "the Messiah". As David Stratton shows in his answer, the Messiah concept is originally Jewish, and Christians believe that Jesus is that very same Messiah, and the fulfilment of various prophecies. But bear in mind that most Christians historically (1) were Gentiles, and (2) lived long after Jesus did. They are not in the position of already believing the Jewish scriptures to contain true prophecy, and then figuring out that they are talking about Jesus - as if they might wake up one day and decide someone else is a better fit. It's more like taking the salvation work of Jesus as basic, and afterwards using that understanding to approach the Jewish tradition. Jesus's Messiah-nature is (pretty much) axiomatic for Christians, and not a conclusion; instead, the facts of his life tell us what "Messiah" ought to mean. 

The earliest Christians, at least, were steeped in the concept of Messiah. As we know, there was a pre-existing expectation of a religious-political saviour of some kind, diverse interpretations of exactly what that meant, and many claimants to the title. The first Christians were those who came to believe that Jesus of Nazareth was the same person as the expected Messiah, and they explained this with reference to the Jewish scriptures (consider Peter's speech in Acts 2:14-41, for just one example). 

I daresay that in many cases, Jewish people, ancient or modern, would regard a lot of these interpretations as wrong or unjustified (though not all: there are several passages that Jews and Christians agree are messianic, even if they disagree on whether they are talking about Jesus). From a Christian perspective, these passages help us to understand who Jesus was - they do not provide criteria against which he should be judged. Remember that Christians read the New Testament as authoritative from the get-go. If it says that's how to understand what Joel wrote, then there you have it. Moreover, it says very clearly that all expectations about the Messiah are met or exceeded in Jesus (see for example the Letter to the Hebrews). In particular, he is a king, a priest and a prophet - but not in the way people expected - he is the suffering servant, he is representative of Israel, he brings God's truth to the world, he is above the angels, and so on. More than that, he uniquely met and defeated sin in his own person, as "the firstborn of the dead" whose resurrection makes eternal life possible for all people.

There is a "weak" version of Jesus-as-Messiah, where "Messiah" was a useful analogy for explaining what Jesus did, to people who were already familiar with the idea. Consider in opposition Acts 17:16-34, where Paul speaking in Athens uses the language of Greek philosophy rather than Jewish prophecy. The title would then be just one of many attributes or analogies used to describe who Jesus was, as he is elsewhere called the bread of life, the lamb of God, and so on. But this isn't really satisfactory, since it doesn't explain why exactly God would choose to be incarnate in this nation, at this time. 

From a Christian perspective, one can understand the entire prior history of Israel, and indeed the world, as leading towards Jesus. This includes the Messiah concept. In other words, the fact that the messianic idea existed should be "explicable" in terms of Jesus. N. T. Wright (Anglican theologian and bishop) writes that for Paul, "In Jesus the Messiah the covenant purpose of the creator for Israel was finally fulfilled" 1. In this way the universal significance of Jesus is tied in with the religious and political context of his life, and all of these circumstances were arranged by God. Messiah is not an empty or minor title. It is inseparable from the gospel message. And because of this there is no objective checklist within Christianity for deciding whether someone is the Messiah. Christian faith presupposes that Jesus is the Messiah.

Here comes a terrible analogy. Suppose I am expecting my long-lost uncle to show up for dinner. I've never met him, but I have some idea what he looks like (and perhaps my family can't agree on how tall he is, whether his hair is greyish-black or blackish-grey, or whether he sings bass or tenor). When he does arrive and introduces himself, I immediately "know" that he is my uncle, by what he says and the way he looks and moves, even if he doesn't precisely match my earlier expectation. He may show other forms of proof too. But from now on, because I know who my uncle is, I have updated my uncle-concept in the light of my new experience. True, there is a definition of "an uncle" as the brother of one of my parents, but my definition of "my uncle", my idea of who he is, comes from the facts of his existence. My understanding of my family history, and of all the stories in which my uncle featured, has changed now that I have met him. I cherish those stories but I no longer use them as a checklist against which uncle-candidates can be assessed. Analogy ends.

1. N. T. Wright. Romans and the theology of Paul. In Pauline Theology, volume 3, ed. David M. Hay and E. Elizabeth Johnson. 1995.