"Mon frère" (My Brother) was used by the French King to address other Kings/Emperors. For example a letter of Louis XVI to Another Monarch from 1791

One great example of this is how Sultan Murad III and Queen Elizabeth I of England addressed each other in letters. They were extremely respectful, but there were some pretty loaded political reasons why this was the case. They had to navigate the space between making themselves sound big and powerful (much of which was still posturing at this point for Elizabeth), and simultaneously showing the utmost reverence for the recipient with whom an amicable political and military relationship was beneficial for both sides.

Murad addresses Elizabeth as follows (Copy/pasted from the transcribed text out of Hakluyt's Principall Navigations collection.): "IN greatnes and glory most renowmed Elizabeth, most sacred Queene, and noble prince of the most mightie worshippers of Iesus, most wise gouernor of the causes and affaires of the people and family of Nazareth, cloud of most pleasant raine, and sweetest fountaine of noblenesse and vertue, ladie & heire of the perpetuall happinesse & glory of the noble Realme of England (whom all sorts seeke vnto and submit themselues) we wish most prosperous successe and happie ends to all your actions, and do offer vnto you such pleasures and curtesies as are worthy of our mutuall and eternall familiaritie: thus ending (as best beseemeth vs) our former salutations."

And Elizabeth, in reply: "ELizabeth by the grace of the most mightie God, and onely Creatour of heauen and earth, of England, France and Ireland Queene, the most inuincible and most mighty defender of the Christian faith against all kinde of idolatries, of all that liue among the Christians, and fasly professe the Name of Christ, vnto the most Imperiall and most inuincible prince, Zuldan Murad Can, the most mightie ruler of the kingdome of Turkie, sole and aboue all, and most souereigne Monarch of the East Empire, greeting, and many happy and fortunate yeeres, with abundance of the best things."

Clearly they're as interested in tooting their own horn as they are in anything else. Bear in mind, this was the collection of letters in which the Sultan really waffled vaguely on his stance toward helping England out should Spain try to invade (which they did, in 1588. And the Ottomans sent no reinforcements. But England kicked booty anyway).

I'm not, like, extrapolating greatly for you, but I thought those quotes might be useful. (I copy/pasted from EEBO, but linked to Project Gutenberg, FYI. So the text may not be super exact.)

(EDIT: Sorry guys! I didn't realize Project Gutenberg had split the Hakluyt text into multiple volumes. I found the exact one I was looking for and changed the link. The text exists as a whole (huge-ass annoying to download) document on EEBO, hence my confusion.)

What about addressing the monarchs of other cultures/religions such as Caliphs, Sultans, etc. How would the European monarchs have addressed them and vice versa?

There's a letter on display at the Morgan Library in NYC right now from Elizabeth I of England to Henry III of France where she addresses him as "Monseiur mon cousin." Can anyone comment on why "cousin" may have been used? They were related, though distantly if I'm not mistaken-but please correct me if I'm wrong!

How would a queen and king as husband and wife addressed each other in private? Somehow I suspect that in public they has to be formal, but in private, was it also Your Majesty, or just My Dear Henry?

The letters of Queen Victoria of the United Kingdom have been published in various places as well; Project Gutenberg is the most straightforward to find.

What is interesting regarding Victoria, is that she was related in some fashion to a great many of the other monarchs of Europe, therefore the letters tend to have a familial and personal tone, but after the updates on health and doings of family and household, almost as an afterthought, they slip in a few sentences regarding matters of state. Of course by this age, many monarchies had something akin to a State or Foreign Affairs office, and parliaments and ministers who conducted diplomacy, but the monarchies seem to have operated as a side-channel for informal statecraft.

Here is Victoria writing to Leopold of Belgium, and his reply (1842):

My dear Uncle,—I have to thank you for a kind, short note of the 27th inst., which I received on Sunday. I gave your kind message to the King of Prussia, who was much touché by it. He is a most amiable man, so kind and well-meaning, and seems so much beloved. He is so amusing too. He is very anxious that Belgium should become liée with Germany, and I think, dearest Uncle, that it would be for the real good of Belgium if it could be so [...]

Leopold's reply:

My dear Victoria,—Thousand thanks for your kind letter of the 1st, which I received yesterday.

The King of Prussia is a very delightful person;13 he is so clever and amiable, and, owing to his good-nature, not by any means fatiguing. I fear you had cold weather yesterday for the opening of Parliament. To-day we have here a tremendous fog; Heaven grant that it may not be so heavy on the Thames! else the King's journey will be rendered difficult. [...] I wish the King may also talk to his helter-skelter cousin in Holland; if the man goes on in his wild intrigues, though he will get most probably nothing by it himself, he may do a great deal of harm, and may force us to incline more towards France for fear of his intrigues with France.

A tad bit earlier than the period you're interested in, but in his letters to the King of Portugal appealing for him to cease to allow traders to travel to his kingdom, Nzinga Mbemba, the king of the Kingdom of Kongo in Africa, referred to the Portuguese King as "Sir, Your Highness..." This may be due to the fact that the messages were in a requesting nature, but the following body of the writings are distinctly conciliatory and beseeching. It feels like a lesser appealing to his superior.