I am starting this thread so that the kind denizens of OrthodoxChristianity.net may post or link to citations from the early Church illustrating how appeals were made to bishops other than that of Rome.
In the patristic period, examples are too numerous to catalogue. Try reading the epistles of St Dionysius of Alexandria, St Gregory of Neocaesaria, St Athansius the Great, St Basil the Great, St Gregory the Theologian, St Amphilochius, St Timothy of Alexandria, St Theophilus of Alexandria, St Cyril of Alexandria, St John the Faster, St Nicephorus the Confessor. The list goes on and on. In the earlier centuries, Alexandria was a common See of appeal, especially for the region. Then, Constantinople, as its prominence rose. Also many other Sees. Bishops would initiate an actual appeal, or simply write a letter asking for guidance on this or that issue. A whole genre arose thereby: The "Question and Answer."
Probably the most convenient place to read examples of this sort in one place would be in a collection of canons, e.g. Rhalles and Potlis, since many such epistles were turned into canons in the East. An interesting aside: In the East, letters of this sort from a variety of Sees and Fathers were turned into canons and placed in the manuscripts after the Ecumenical canons; in the West, that position was occupied by Papal decretals. This happened as early as the sixth century. One can thereby see how differences in common sources can create different understandings of what is "normal." Anyway, the patristic canons are only the most popular examples. The act of appeal to nearby or powerful Sees was so common it is pervasive in epistolary literature, and continues throughout Church history.
For the early medieval period through the high medieval period, see Will's
Acta et scripta quae de controversiis ecclesiae graecae at latinae saeculo undecimo composita extant. Lots of interesting back and forth between the various Patriarchates and other episcopal sees on issues of jurisdiction and Latin vs Greek practices.
For the later medieval period, see Miklosich and Müller's
Acta Patriarchatus Constantinopolitani, Acta et Diplomata Graeca medii Aevi Sacra et Profana.