There are a few things I would add to Nathaniel's answer.
There are additional points which may be drawn from the text.
As noted the selection of Matthias came before the outpouring of the Holy Spirit. It also came after Jesus had given commands through the Holy Spirit to the apostles whom He had chosen:
In the first book, O Theophilus, I have dealt with all that Jesus began to do and teach, until the day when he was taken up, after he had given commands through the Holy Spirit to the apostles whom he had chosen. He presented himself alive to them after his suffering by many proofs, appearing to them during forty days and speaking about the kingdom of God. (Acts 1:1-3 ESV)
Several things stand out. First, is the emphasis on "the apostles who He had chosen." Obviously Jesus did not see the deficiency caused by Judas' death as something which required immediate action to correct. The instruction to wait to preach was made with full knowledge this would be done with the 11 He chose not 12. Later Jesus personally chose Saul to be His chosen instrument "to carry my name before the Gentiles and kings and the children of Israel." (Acts 9:15) Whether Peter acted preemptively (I think he did), it is clear Jesus chose Paul, just as He chose the others and it is equally clear Jesus purposely did not choose Matthias either to be one of the 12, or to be included in the instruction (Acts 1:2) during the 40 days. His only claim to apostleship is selection by lot.
Another aspect is the emphasis on "commands through the Holy Spirit." Luke is purposeful to state the teaching was not by Jesus alone but through the Holy Spirit. This makes the absence of the Holy Spirit in the selection process of Matthias more pronounced. Not only is the Holy Spirit not mentioned by Peter, the vast majority of the 120 disciples had not received the Holy Spirit.
The Holy Spirit is not mentioned again until the outpouring on the Day of Pentecost. Those who claim Peter acted under the guidance of the Holy Spirit, ignore the possibility the Holy Spirit went with Jesus at the Ascension and returned a few days later. A sequence of the Holy Spirit ascending with Jesus and returning at Pentecost resolves many of the issues raised by Jesus giving the Spirit by breathing on the disciples (John 20:22-23) and the later outpouring. A short absence of the Holy Spirit before returning would only impact the events during that period. Additionally, Jesus sending the Holy Spirit makes more sense if the Holy Spirit is actually with Jesus in heaven. 1
Finally, Peter makes reference to the necessary qualifications to be considered as a replacement for Judas; his focus is on the Resurrection and what Jesus did. Peter's qualification is one had to be present from the beginning, as were the first 12. However logical this seems, it ignores Jesus purpose for choosing Saul:
But the Lord said to him, “Go, for he is a chosen instrument of mine to carry my name before the Gentiles and kings and the children of Israel. (Acts 9:15 ESV)
Saul, as a Roman citizen was much better qualified for this purpose. Saul's citizenship made travel easier and would ultimately gain him access to Caesar, something Matthias had no legal standing to request. In terms of being an apostle to the Gentiles, Saul was far more qualified than Matthias. This also serves to highlight the presumptive nature of Peter's actions. The disciples were inwardly focused on the Kingdom of Israel (Acts 1:6). Obviously Jesus had plans for a bigger mission
Choosing 12 to be apostles is purposeful to mirror the 12 tribes:
that you may eat and drink at my table in my kingdom and sit on thrones judging the twelve tribes of Israel. (Luke 22:30 ESV)
While the exact listing of the 12 tribes varies, all tribes trace their origin back to one of Jacob's children. The last child was Benjamin. The tribal ancestry of the first 12 apostles is not given, but Saul was of the tribe of Benjamin:
I ask, then, has God rejected his people? By no means! For I myself am an Israelite, a descendant of Abraham, a member of the tribe of Benjamin. Romans 11:1 ESV)
Thus the last apostle chosen by Jesus was from the tribe of Benjamin. Since the background of the other apostles is unknown, how much significance should be placed on this one fact is questionable. However, focusing on the birth differences with Benjamin relative to his siblings brings other differences to light. First, 11 boys and 1 girl were born in Paddan-aram2 and Benjamin was born in Israel. Thus birthplace sets Benjamin apart from his siblings. Again, we do not know the birthplaces of the first 12 but is is not unreasonable to assume they were born in Israel. Saul however, was born outside of Israel in Tarsus:
“I am a Jew, born in Tarsus in Cilicia, but brought up in this city, educated at the feet of Gamaliel according to the strict manner of the law of our fathers, being zealous for God as all of you are this day. (Acts 22:3 ESV)
If the other apostles were born in Israel, this would be another parallel to Benjamin.
One fact which is not in dispute is the location of everyone's place of re-birth. All of the original apostles became children of God in Israel. Saul did not. Saul's rebirth place was outside of Israel; likewise Saul is different from the other 11 in that he alone was baptized by a Christian and in the name of the Father, and of the Son, and of the Holy Spirit.
There are a number of undisputed differences between Matthias and Saul:
- Method of selection - Matthias was chosen by lot; Saul was chosen by Jesus.
- Location of selection - Matthias was chosen in Israel; Saul was chosen outside Israel.
- Location of re-birth - Matthias was re-born in Israel; Saul was re-born out side Israel.
- Method of baptism - Matthias was baptized by John the Baptist before the Resurrection in Israel; Saul was baptized by Christians after the Resurrection outside of Israel.
- Citizenship - Matthias was not a Roman citizen; Saul was a Roman citizen
In terms of having a person who would be an apostle to the Gentiles and Kings, Paul was more qualified than Matthias or any of the original apostles.
1. Pentecost is to be 50 days after the Sabbath following the Passover which would be 50 days after the Resurrection (which was the day of the Feast of Fruits.) The actual start of the 40 days period is not specified. If it begin immediately with the Resurrection, the interval between Ascension and Pentecost would be 10 days. Luke seems to be making an allusion to Genesis 1, where the Spirit was over the waters before God's work of creation begin (with no mention of the presence of the Holy Spirit during the period of work). In other words, just as the Spirit is found in the beginning of Genesis and the presence is implied but never stated, Acts opens by following the same pattern: the Spirit is on the earth and the presence is implied but never stated until the outpouring on Pentecost.
2. Jacob's first 12 consisted of 11 boys and 1 girl. One of the first 12 was clearly different from the other 11. This pattern was true of the first 12 apostles and 1 "was a devil." This does not mean Dinah was a devil. It is just an observation the numerical similarities go beyond the obvious 12 sons of Jacob, a fact which seemingly Peter overlooked.