When did the malachim come to Avraham about the birth of Yitzchak?

The Gemara in Rosh Hashana (11a) seems to say that they came on Sukkos (or according to Tosafos 2 days before Sukkos) and that is when the whole story at the beginning of this weeks parsha (וירא) happened.

Tosafos and other Rishonim are bothered by a number of questions:
1. The medrash tanchuma (quoted by Rashi on Chumash) contradicts the Gemara and says that the whole story happened on Pesach
2. The pasuk at the end of Parshal Lech Lecha (right after Hashem commands Avraham to do a bris mila) says that Sarah will have a baby "למועד הזה לשנה אחרת". If Avraham's bris was right before Succos (on YK according to Tosafos) and Yitzchak was born on Pesach how is that "לשנה אחרת" it is the same year.

Tosafos and the Ritva answer that the gemara here is according to R' Yehoshua and the medrash is like R' Eliezer. According to R' Yehoshua that the world was created in Nissan, the story happened on Succos and the next Pesach is in the next year. However, according to R' Eliezer that the world was created in Tishrei, the story could not have happened on Succos, because Pesach is in the same year, therefore it happened on Pesach like the Medrash.

This is very difficult because the Gemara in Rosh Hashana is detailing all the נפקא מינא and machlokes between R' Yehoshua and R' Eliezer based on when the world was created. If Tosafos is right why didn't the gemara list this as well?

The Maharsha has a different p'shat and tries to reconcile the Medrash and the Gemara as follows:
The Gemara and Medrash don't conflict they are talking about different things. The pasuk in לך לך that says "למועד הזה לשנה אחרת", happened on Pesach. The malachim came on Pesach. However, when Hashem asks Avraham why Sarah laughed and then says "למועד אשוב אליך" that happened in Tishrei on Succos. This answers the contradiction but raises additional questions.

It is very difficult to read the pesukim this way. The malachim come on Pesach and tell Avraham that he will have a son and Sarah laughs. Six months later on Succos Hashem comes back and asks Avraham why Sarah laughed and promises again that he will have a son on pesach. Then the story shifts back to the malachim leaving on Pesach and Avraham arguing with Hashem about S'dom. You have a very strange shift in time from Pesach to Sukkos, back to Pesach.

According to the Maharsha the Gemara in Rosh Hashana by פקידה is also very difficult. The Gemara says that Sara was נפקדה on Rosh Hashana. Yet, the malachim came on Pesach and told Avraham that he would have a son, when was the pekida? It would seem that it was 9 months before (the Rosh Hashana before). However, Sarah did not actually become pregnant until after the next Succos (as the Gemara says), over a year after the pekida! The Maharsha answers that even though on Pesach the malachim told Sara that she would have a baby,the pekida (the gezera that she would get pregnant) was only 5 months later on Rosh Hashana. IMHO, this is very difficult. The malachim are bringing a message from hashem on Pesach that she will have a baby next Pesach. She is going to have a baby, Hashem said so. Therefore what on earth does the pekida on Rosh Hashana mean? It already happened on pesach that she is going to have a baby.

In fact, the Maharasha refers you to a Tosafos in Bava Kama 92a (ד"ה כאשר) who makes exactly this point. Tosafos asks, if the malachim came on Pesach how could the pekida be later on Rosh Hashana? Tosafos answers the pekida was not that she would become pregnant but rather that the pregnancy and birth would be easy. Tosafos is explicitly against the Maharsha.

Tosafos's (Bava Kama) answer is also very difficult. The gemara says that 3 women were nifkad on Rosh Hashana (Sara, Rachel, and Chana). By Rachel, the pasuk says explicitly that Hashem remembered her (זכירה) and ויפתח את רחמה. The pasuk explicitly states that the pekida was with regards to getting pregnant. Since the gemara equates the 3 women (and learns them out 1 from the other) the pekida by Sarah must be the same thing, regarding getting pregnant and therefore how can Tosafos say that the pekida was with regards to having an easy pregnancy and birth.