The very first extant list of of the first Bishops of Rome that we have is that of St. Irenaeus (Adv. Haer. 3.3.3):
The blessed apostles, then, having founded and built up the Church, committed into the hands of Linus the office of the episcopate. Of this Linus, Paul makes mention in the Epistles to Timothy. To him succeeded Anacletus; and after him, in the third place from the apostles, Clement was allotted the bishopric. This man, as he had seen the blessed apostles, and had been conversant with them, might be said to have the preaching of the apostles still echoing [in his ears], and their traditions before his eyes. Nor was he alone [in this], for there were many still remaining who had received instructions from the apostles. In the time of this Clement, no small dissension having occurred among the brethren at Corinth, the Church in Rome despatched a most powerful letter to the Corinthians, exhorting them to peace, renewing their faith, and declaring the tradition which it had lately received from the apostles, proclaiming the one God, omnipotent, the Maker of heaven and earth, the Creator of man, who brought on the deluge, and called Abraham, who led the people from the land of Egypt, spake with Moses, set forth the law, sent the prophets, and who has prepared fire for the devil and his angels. From this document, whosoever chooses to do so, may learn that He, the Father of our Lord Jesus Christ, was preached by the Churches, and may also understand the apostolical tradition of the Church, since this Epistle is of older date than these men who are now propagating falsehood, and who conjure into existence another god beyond the Creator and the Maker of all existing things. To this Clement there succeeded Evaristus.
We have the letter of St. Clement to which Irenaeus refers, which does say what Irenaeus says, although these things are not particularly singled out (Irenaeus is focusing on them because his point is that already with Clement we have a clear expression of the tradition that Gnostics deny or treat as a superficial guise for their views). Irenaeus had been to Rome, and had fairly good connections to it, so our best early list of the first bishops of Rome is: St. Linus, St. Anacletus, St. Clement.
Tertullian, who knew the Roman traditions, tells us this (Praescr. Haer. 32):
But if there be any (heresies) which are bold enough to plant themselves in the midst of the apostolic age, that they may thereby seem to have been handed down by the apostles, because they existed in the time of the apostles, we can say: Let them produce the original records of their churches; let them unfold the roll of their bishops, running down in due succession from the beginning in such a manner that bishop shall be able to show for his ordainer and predecessor some one of the apostles or of apostolic men, — a man, moreover, who continued steadfast with the apostles. For this is the manner in which the apostolic churches transmit their registers: as the church of Smyrna, which records that Polycarp was placed therein by John; as also the church of Rome, which makes Clement to have been ordained in like manner by Peter.
So Tertullian seems to suggest that Clement was ordained as bishop of Rome directly by Peter.
The fourth century Liberian Catalog gives us a different order: Linus, Clement, Cletus. But the Liberian Catalog does not seem to be very reliable.
Also in the fourth century, Jerome gives us the view of things as they were understood then (De Vir. Ill. 15):
Clement, of whom the apostle Paul writing to the Philippians says “With Clement and others of my fellow-workers whose names are written in the book of life," the fourth bishop of Rome after Peter, if indeed the second was Linus and the third Anacletus, although most of the Latins think that Clement was second after the apostle.
So Jerome tells us that the general Latin view was that Clement followed directly after Peter, but recognizes that there is a tradition in which he is third after Linus and Anacletus.
One of the things that probably trips us up a bit is in assuming that things were originally divided up as they are today. This is sometimes put as a denial that the primitive church had a "monarchical episcopacy", but this is an extremely misleading way of stating things; the phrase doesn't usually seem to mean anything, and we know that if we take it to mean 'one bishop to a city', this rule wasn't formally imposed until the First Council of Nicaea, although for purely practical reasons this was already the state of things by then in most parts of the Empire (and outside it). Bishops are heads of communities, and nothing actually requires that a city have only one territorial bishop (outside of practical convenience and, after Nicaea, canon law) because nothing requires that it be organized as only one community. The reason for saying all of this is that the Liber Pontificalis (which was first compiled, probably, in the fifth century, although it seems to have been heavily revised at times since) gives us an account that includes both traditions and seems to have something like this in view. Speaking of Peter, it says:
He ordained two bishops, Linus and Cletus, who in person fulfilled all the service of the priest in the city of Rome for the inhabitants and for strangers; then the blessed Peter gave himself to prayer and preaching, instructing the people....
He consecrated blessed Clement and committed to him the government of the see and all the church, saying: "As unto me was delivered by my Lord Jesus Christ the power to govern and to bind and loose, so also I commit it unto thee that thou mayest ordain stewards over diverse matters who will carry onward the work of the church, and mayest thyself not become engrossed with the cares of the world, but mayest strive to give thyself solely to prayer and preaching to the people."
Thus the Liber Pontificalis seems to envisage a scenario in which Rome had a period in which there were at least two and possibly three bishops of Rome, not counting Peter himself, who as apostle was above them all, but that they had different functions. Linus and Cletus oversaw the spiritual needs of the people of the city (possibly with Linus devoted to residents and Cletus devoted to pilgrims and travelers), and then at some point -- it makes it sound like it was a later arrangement -- gave authority over Rome to Clement. However, while the work lists Linus and Cletus, it makes clear that it accepts the tradition that Clement was first after Peter:
Therefore Linus and Cletus are recorded before him for the reason that they were ordained bishops also by the chief of the apostles to perform the priestly ministry.
Thus, Clement is the first in line after Peter, but Linus and Cletus are bishops charged with lesser duties, who seem to get an honorary placement, presumably because they were bishops of Rome ordained before Clement, although they were not like Clement the successor of Peter.
This solves the problem of whether Clement was first or third quite neatly. It does so in a way that suggests a much earlier tradition, since if it were not based on something earlier, one might expect (as happened later) a simplification of the list without this complicated "Linus and Cletus are first, but not actually first" bit. It's even a solution that has a great deal of plausibility both in itself and insofar as it would explain the divergent traditions, but we don't know much about the sources the Liber Pontificalis used, or how far back this idea actually goes, and one could perhaps argue that this is the author's attempt to try to reconcile two different traditions.
In any case, this seems to be the lay of the land as far as the textual evidence goes.
