Was die Anreden angeht, so wurden die letztgültig erst auf dem Wiener Kongreß (1814/15) festgelegt. Die dort festgelegten Formen gelten im Grunde bis heute.
Im Mittelalter wurden Könige als "Eure Hoheit" oder "Sire" angesprochen. Erst Kaiser Karl V. (1519–1556/58) hat für sich das Majestätsprädikat erkoren, da er meinte, ein Kaiser bräuchte auch eine über den Königen stehende Anrede. Freilich haben kurz darauf auch Franz I. von Frankreich (1515–1547) und Heinrich VIII. von England (1509–1547) begonnen, sich "Majestät" zu nennen. Die spanischen Könige beanspruchten diese Anrede ebenso. M. W. hat der Kaiser aber erst im Westfälischen Frieden (1648) das Majestätsprädikat des französischen Königs anerkannt. Das der spanischen Verwandtschaft erkannte man wohl bereits ab Philipp II. (1556–1598) an (Quellenverweise würde ich begrüßen, mir liegt gerade nichts vor).
Die Kurfürsten bekamen, soweit ich weiß, bereits von Karl IV. (1346/47–1378) die Anrede "Kurfürstliche Durchlaucht(igkeit)" zugestanden.
Herzöge erlangten erst im Laufe der Zeit das Prädikat "Durchlaucht". Früher war "Hochgeboren" üblich (wohl bis ins 17./18. Jh.).
Fürstlichen Grafen steht seit dem Wiener Kongreß das Prädikat "Erlaucht" zu. Die anderen müssen sich mit "Hochgeboren" begnügen.
Freiherren, Ritter, Edle und untitulierter Adel wird mit "Hochwohlgeboren" angesprochen, wobei es hier auch feine Unterschiede gibt ("Hoch- und Wohlgeboren" kam mir auch schon unter).
Die Rangfolge im Protokoll war eine sehr komplizierte Sache, die oft für Streit sorgte. Man denke nur an die Verhandlungen am Ende des Spanischen Erbfolgekrieges, wo ja der kaiserliche Bevollmächtigte und der Ludwigs XIV. auf Gleichrangigkeit bestanden, was die Friedensverhandlungen enorm in die Länge zog (ich glaube, man einigte sich dann darauf, daß beide gleichzeitig durch zwei verschiedene Türen den Verhandlungsraum betreten sollten). Das klingt heute affig, aber damals war das absolut essentiell.
Ein ähnlicher Fall war der Besuch des Mainzer Kurfürsten bei Kaiser Karl VI. in Wien 1731. Da war ganz genau festgelegt, wie viele Schritte dieser auf den Kaiser zu gehen mußte und wie viele der Kaiser auf ihn (natürlich sehr viel weniger).
Die protokollarische Rangfolge am kaiserlichen Hof in Wien war m. W. so, daß der spanische Botschafter den Vorrang vor allen anderen hatte (das kommt sicher daher, weil die Hauptlinie der Habsburger bis 1700 in Spanien regierte). Danach müßte der französisische Botschafter gekommen sein, danach der englische. An den anderen Fürstenhöfen Europas hatte freilich der kaiserliche Botschafter den Vorrang.
Auch wenn Philipp II. von Spanien in der 2. Hälfte des 16. Jhs. und Ludwig XIV. von Frankreich in der 2. Hälfte des 17. Jhs. fraglos die mächtigsten Herrscher Europas waren: protokollarisch standen sie immer hinter dem jeweiligen Kaiser des Heiligen Römischen Reiches. Zeitlebens haben weder Philipp II. noch Ludwig XIV. diesen Zustand wirklich akzeptiert. Beide hatten Ambitionen auf die Kaiserkrone. So stand es in den 1580er/90ern sogar im Raum, Rudolf II., den Neffen Philipps, durch ihn zu ersetzen. Und der Sonnenkönig kandidierte 1657/58 ganz offiziell gegen Leopold von Habsburg, den späteren Leopold I. Noch in den 1680ern versuchte Ludwig XIV., den brandenburgischen Kurfürsten dazu zu verpflichten, ihn bei der nächsten Wahl eines Römischen Königs zu wählen. Infolge der reichsfeindlichen Politik des Sonnenkönigs ab spätestens 1688 war eine bourbonische Kaiserkandidatur allerdings zum Scheitern verurteilt (1690 wählte man vivente imperatore Joseph von Habsburg, alias Joseph I., Leopolds ältesten Sohn).