С господами и сударынями мы уже разобрались вот здесь, давайте же теперь посмотрим, откуда происходят обращения в других языках.
Мистер: mister < master < magister (лат. "учитель, предводитель, начальник"), от корня *meg ("большой, великий"). От него мы можем знать латинское прилагательное "magnus" ("великий"), ну и интернациональное слово "макси".
Любопытно, что антонимом слова "magister" был "minister" (узнаете слово "мини"?), которое переводилось как "слуга, помощник". А теперь министр стал значительно круче.
Французским аналогом мистера является "мэтр" ("maître").
Миссис: missis < mistress, женский род от мистера.
У французов это слово выглядит как "maîtresse", что может означать очень разные вещи - "учительницу", "хозяйку" и "любовницу" (видимо, тут французы заложили разные женские роли, кем мы там должны быть на кухне, кем в салоне, и так далее).
Мисс: miss < mistress, просто сокращенная форма.
Мсье: monsieur < mon sieur < mon seigneur, что значит "мой господин". Думаю, что вариант "монсеньёр" тоже все слышали, как и устаревшие "сир" и "мессир".
Мадам: madame < ma dame, то есть "моя дама". Французское слово "dame" происходит от латинского "domina", что значит "хозяйка" (слово "доминировать" оттуда же).
То же самое - испанские "дон" и "донья", португальские "дон" и "дона".
Мадемуазель: ma demoiselle < ma damoisele, просто та же "дама", но с уменьшительным суффиксом, получается "моя дамочка".
Сеньор: señor < senior (лат. "старший"). Это то же слово, которое мы видели во французском ("сир", "сеньёр").
Херр: herr < hērro ("серый, седой")\hēr ("уважаемый, благородный"). Это чисто германское слово, но логика в нем та же, что и в латинском: седой, значит старый, значит самый старший, значит самый умный, значит самый крутой и уважаемый.
Фрау: frau < frouwa ("хозяйка, госпожа") < *frawan (прагерм. "хозяин, господин"). А это слово родственно нашему "правый", а по сути ближе к слову "правитель".
Фройляйн: Fräulein - уменьшительное от "Frau"