Could someone tell me what the earliest Papal statement or encyclical was where the Church condemned the institution of slavery? A Magisterial document would also be accepted if there are earlier teachings by the magisterium.
Condemnation of 'unjust' slavery came somewhat earlier than papal condemnation of 'just' slavery. The legitimacy of slavery was recognised in the Corpus Iuris Canonici, promulgated by Pope Gregory IX, and this implicit acceptance of slavery was not removed until 1913. Jean Allain (The Legal Understanding of Slavery, page 20) says the Corpus Iuris Canonici was not as explicit in its treatment of the issue as were the civil laws, but that students of the canon law would have found no contradiction.
According to Wikipedia, Cardinal Avery Dulles makes the observations that no Father or Doctor of the Church was an unqualified abolitionist, and that no pope or council ever made a sweeping condemnation of slavery as such, but that they constantly sought to alleviate the evils of slavery and repeatedly denounced the mass enslavement of conquered populations and the infamous slave trade, thereby undermining slavery at its sources.
Nevertheless, there were some papal pronouncements that provided qualified condemnation of slavery. Pope Eugene IV issued a Papal bull, Creator Omnium on 17 December 1434, excommunicating anyone on the Canary Islands who enslaved newly-converted Christians, but offering no protection to those who declined to become Christians.
Further on, Wikipedia tells us that in 1888, Pope Leo XIII issued a letter to the Bishops of Brazil and another in 1890, Catholicae Ecclesiae (On Slavery In The Missions). In both these letters the Pope singled out for praise twelve previous Popes who had made determined efforts to abolish slavery. Five of the Popes praised by Leo issued documents that authorized enslavement as an institution, as a penalty for ecclesiastical offences, or when arising through war, but Leo's letters make no distinction between "just" and "unjust" forms of slavery and have therefore been interpreted as a condemnation of slavery as an institution.
The Vatican II document Gaudium et Spes ('Pastoral Constitution on the Church in the Modern World', 1965) stated:
The varieties of crime are numerous: all offenses against life itself, such as murder, genocide, abortion, euthanasia and willful suicide; all violations of the integrity of the human person, such as mutilation, physical and mental torture, undue psychological pressures; all offenses against human dignity, such as subhuman living conditions, arbitrary imprisonment, deportation, slavery, prostitution, the selling of women and children, degrading working conditions where people are treated as mere tools for profit rather than free and responsible persons: all these and the like are criminal: they poison civilization; and they debase the perpetrators more than the victims and militate against the honor of the creator.
Pope John Paul II said, in Fidei Depositum, "May the light of the true faith free humanity from ignorance and slavery to sin in order to lead it to the only freedom worthy of the name ..." In 1993, he apologised for Catholics' involvement with the African slave trade.
The Catechism of the Catholic Church published in 1994 sets out the official position of the modern Church:
CCC 2414 The Seventh Commandment forbids acts or enterprises that ... lead to the enslavement of human beings, to their being bought, sold and exchanged like merchandise, in disregard for their personal dignity. It is a sin against the dignity of persons and their fundamental rights to reduce them by violence to their productive value or to a source of profit ..."