The "Fea" of men (spirit) do leave "Ea" ("The World that Is") after death.
Tolkien has repsented "Ea" as the embodiement and living out of a Grand Theme of music (cf "Music of the Ainur") - essentially a Drama or Story, designed by Eru and adorned by the actions of his created beings (from Ainur to Quendi, Atani, Dwarves, etc). Thus, he talks in some of his Letters (eg #200) about the Valar being required to "remain in it 'until the story was finished'".
Men (and Hobbits as a branch of Atani) have a special gift to be able to leave the story and step OUTSIDE (where they, perhaps, can watch the story unfold). Given that Tolkien was a devout Christian (& Catholic) it seems a fair presumption that, upon leaving Ea, they would dwell in the Halls of Eru (the "Void" simply being the places outside Ea that are not dwelling places of Eru and the Ainur).
Saying Mandos "sends" the spritis of Men, etc "may" not be fully accurate. I've thought that their Fea depart the world (by the gift of Eru) and their destination thereafter is no longer in the hands of the Valar. Whether they travel on their own, or are escorted by Ainur (or by Eru himself) is speculation - I've not heard/read anything about that by Tolkien.
On their time in Aman, Tolikien (in Letter 246) states of Frodo that "he went to both a purgatory and to a reward, for a while: a period of reflection and peace and a gaining of a truer understanding of his position in littleness and greatness, spent still in Time amid the natural beauty of 'Arda Unmarred'." To "be healed - if that could be done, before he died." Sam, presumably, would have a similar experience.
Gimli, being a Dwarf, is a bit of an odd case. Aule made the Dwarves (tho Eru gave them a place in his creation) but there are uncertain reports or beliefs by Dwarves and others about their fate after "dying". They believe they go to Mandos and their wait the end when they will aid Aule in the remaking of Arda. But it is never said certainly whether that belief is accurate or not.
Silmarillion says that it is believed (by the Valar) that Atani (Men) will join in the Second Music of the Ainur after the end of Ea, but that Eru has not revealed what he has in store for Quendi (Elves). "Morgoth's Ring" has a section "Athrabeth Finrod ah Andreth" which discusses this in some detail and especially how this requires a special Trust and Hope (Estel) of the Eldar. They know they will live till the end of Ea, but have NO PROMISE of surviving after that, while Men have the promise of dwelling eternally with Eru (tho they live only a short time with Ea before "dying").
About Legolas being Oropher? I've never read anything by Tolkien that suggested such was the case. And, as Galadriel55 noted, Tolkien shifted to going with the rebodying of slain Eldar - which meant they were rebodied by the Valar in Valinor. Only in very unusual cases would they then manage to travel back to Middle Earth (Glorfindel is the only such case I'm aware of).
For your Q2, I think it's important to consider you are working from an extremely small sample-set. You mentioned three cases (Beren/Luthien, Tuor/Idril & Aragor/Arwen). I can think of exactly Two other cases in the whole history of Arda ...
- Imrazor and Mithrellas. Imrazor was, per legend, the father of the first lord of Dol Amroth. Mithrellas was a maiden companion of Nimrodel.
- Aegnor (brother of Finrod) and Andreth (women of the house of Beor)
The latter was never consumated, but the Athrabeth makes clear Aegnor's love for Andreth was real, and only wisdom led him to forbear - for Andreth's sake (a whole other discussion).
So, only 5 cases in all of history. And one of those was a male Elf loving a Female Human. Not purely according to odds of pure chance, but if you flipp a coin 5 times - there will be occasions when you get 4 heads and 1 tail.
Then, too, it could be a simple case of Human Men (in such times of unrest and war and danger) tend to travel to seek out Elves more than either human women traveling or any elves seeking out men. Thus there will be more meetings between Human Men and Elvish Females than the opposite.