If Pope St. Stephen's opinions carried no more weight than those of any other bishop, why would St. Cyprian so concern himself with them?
Why consult the Pope at all?
I think you are setting up false dichotomies.
Just because St Cyprian rejected any form of papal supremacy doesn't mean that he wouldn't consult with the Pope. In fact he had already had to send several letters to the previous Pope urging him to take action in certain cases. In his own letters St Cyprian writes against a primacy saying:
"Since you have desired that what Stephen our brother replied to my letters should be brought to your knowledge, I have sent you a copy of his reply; on the reading of which, you will more and more observe his error in endeavouring to maintain the cause of heretics against Christians, and against the Church of God ... He forbade one coming from any heresy to be baptized in the Church; that is, he judged the baptism of all heretics to be just and lawful (Epistle 73.1-2).
Does he give glory to God, who affirms that sons are born to God without, of an adulterer and a harlot? Does he give glory to God, who does not hold the unity and truth that arise from the divine law, but maintains heresies against the Church? Does he give glory to God, who, a friend of heretics and an enemy to Christians, thinks that the priests of God, who support the truth of Christ and the unity of the Church, are to be excommunicated? (Epistle 73.
But let these things which were done by Stephen be passed by for the present, lest, while we remember his audacity and pride, we bring a more lasting sadness on ourselves from the things that he has wickedly done (Epistle 74.3).
But that they who are at Rome do not observe those things in all cases which are handed down from the beginning, and vainly pretend the authority of the apostles ... There is no departure at all from the peace and unity of the Catholic Church, such as Stephen has now dared to make; breaking the peace against you (Cyprian), which his predecessors have always kept with you in mutual love and honour (Epistle 74.6).
I (Firmilian) am justly indignant at this so open and manifest folly of Stephen, that he who so boasts of the place of his episcopate, and contends that he holds the succession from Peter, on whom the foundations of the Church were laid, should introduce many other rocks and establish new buildings of many churches; maintaining that there is baptism in them by his authority (Epistle 74.17).
Stephen is not ashamed to assert and to say that remission of sins can be granted by those who are themselves set fast in all kinds of sins, as if in the house of death there could be the layer of salvation ... But indeed you are worse than all heretics ... you take away from them remission of sins, which is given in baptism, by saying that they are already baptized and have obtained the grace of the Church outside the Church (Epistle 74.22-23).
How great sin have you (Stephen) heaped up for yourself, when you cut yourself off from so many flocks! For it is yourself that you have cut off. Do not deceive yourself, since he is really the schismatic who has made himself an apostate from the communion of ecclesiastical unity. For while you think that all may be excommunicated by you, you have excommunicated yourself alone from all (Epistle 74.24).
And yet Stephen is not ashamed to afford patronage to such in opposition to the Church, and for the sake of maintaining heretics to divide the brotherhood and in addition, to call Cyprian "a false Christ and a false apostle, and a deceitful worker." (Epistle 74.26).
Basilides, after the detection of his crimes, and the baring of his conscience even by his own confession, went to Rome and deceived Stephen our colleague, placed at a distance, and ignorant of what had been done, and of the truth, to canvass that he might be replaced unjustly in the episcopate from which he had been righteously deposed (Epistle 67.5).
But which of us is far from humility: I, who daily serve the brethren, and kindly receive with good-will and gladness every one that comes to the Church; or you, who appoint yourself bishop of a bishop, and judge of a judge, given for the time by God? (Epistle 68.3)."
The last quotation is especially aposite.
I do not doubt the primacy in some sense of the Pope of Rome in the past, but it must be measured by practice and canons.
I am still not sure why the historic primacy of Rome is important. Rome is not Orthodox. There is no Orthodox Pope to have the primacy. If a primacy is necessary for the Church then it has fallen to the Ecumenical Patriarch to serve in that capacity. You should be asking in what sense he
has a primacy.
And of course it is not the case that the Roman practice has prevailed. There are many Orthodox Churches who take an entirely Cyprianic view. My own does for instance.