I am excerpting parts of Ramba"m, Hilchot Kiddush Hachodesh, as I believe are relevant to your question. In summary, the 2 day Yom Tov was based on the distance that messangers could travel within the first 10 days of the month (based on # of allowable travel days for Tishrei. It seems that calculation of the 1st day of Succot was most important. Rosh Hashanna had already been established as 2 days even in Israel, according to most opinions. Yom Kippur, I think, was made 1 day even in Galut b/c of the danger of fasting 2 days - have to check this further.) as well as the establishment of Jews in that village during time of Sanhedrin. Now, the two day celebration is based on following the previous custom and according to Ramab"m is takanat sofrim.
As you already saw, the doubt of Rosh Hodesh is different, as even those in Israel weren't sure, so potentially, every month could have days Rosh Hodesh. It didn't happen that way, but I believe there were times when you had 2 consecutive months with 2 days Rosh Hodesh, depending on when witnesses appeared. While Ramba"m doesn't outrightly state this, I infer that those in the far distances who had the doubt of having to observe 2 days Yom Tov, also observed 2 days Rosh Hodesh every month. (Would appreciate if someone could confirm or refute this.
Mishneh Torah, Sanctification of the New Month 3:11-12:
Every place that the messengers reach, they'd make the festivals a one
day holiday as is written in the Torah. And the distant places that
the messengers wouldn't reach would make two days because of the
doubt, for they wouldn't know which day was the day that the court
fixed the first of the month. There are places that the messengers of
Nissan would reach them and the messengers of Tishri would not reach
them. And according to the law, they ought to make Passover one day of
holiday, for the messengers reached them and they knew on which day
the first of the month was fixed. And they ought to make the holiday
of the festival of Tabernacles two days, for the messengers didn't
reach them. And in order not to distinguish between the festivals, the
sages amended that any place that the messengers of Tishri didn't
reach would make two days [of holidays], even the holiday of Ceasing
Mishneh Torah, Sanctification of the New Month 3:13:
And how much is between the messengers of Tishri and the messengers of
Nissan? Two days. For the messengers of Tishri didn't travel on the
1st of Tishri because it is a holiday and not on the 10th of it
because it is the Day of Atonement.
Mishneh Torah, Sanctification of the New Month 5:12:
A place that has between it and between Jerusalem 10 days or less than
10, and it is [in] Syria or the outside of the land [of Israel], and
they don't have a custom. Or it is a newly formed city in the desert
of the land of Israel. Or a place that [people of] Israel dwells now.
They make two days like the custom of the majority of the world. And
every second day holiday is from the words of the scribes and even the
second day of the holiday of Rosh Hashanah which everyone makes at
Rmaba"m's discussion is mainly in chapters 4 and 5, and, to get a better perspective, you should read the majority of these chapters. The English translation was copied from sefaria.org.
In summary, we aim to get 1 day for both. Rosh Hodesh has its "internal" problem both because of the moons orbit which is not a full day, and when witnesses appear. However, once we know when Rosh Hodesh really was, we can't correct time that already passed (i.e. we can't "correct" Rosh Hodesh itself If people already observed the 1st day, and it was a 30 day but it really was 29.) However, once we know which day really was Rosh Hodesh, we attempt to inform people of that, afterwards. But, there is only so much time and distance that messengers can travel, so they are ALWAYS doubtful.
There is a separate discussion in Ramba"m in ch. 5, I believe that discusses if the date of Rosh Hodesh can be "reverted" retroactively. See there. It's somewhat tangential to answering this question, and I didn't want to cite from it, here.