The first Rashi’s on chumash asks why the Torah begins with the story of creation instead of with the first mitzvah of kiddush hachodesh. Rashi answers that the story of creation serves to justify our right to Eretz Yisrael. Since G-d is the Creator, he has right of eminent domain and can award land to whomever he chooses. Last week I presented Rashi’s answer as a negation or retraction of his hava amina – the pragmatic need to justify our right to Eretz Yisrael forces us to abandon the logical starting point of Kiddush hachodesh in deference to the priority of answering our critics.
The Kli Chemdah does not see Rashi's answer as a retraction of his hava amina. His approach is build around the view of Ramban, who writes (VaYikra 18) that the Torah is ideally meant to be fulfilled only in Eretz Yisrael. The observance of mitzvos outside of Eretz Yisrael is just practice until we can achieve that ideal goal. Ramban later in Sefer Braishis writes that Ya’akov Avinu married two sisters contrary to Torah law because at that time he was residing outside Eretz Yisrael where the obligation to perform mitzvos is not in full force.
Why does the Torah not start with the details of the first mitzvah, kiddush hachodesh? Because the observance of mitzvos in an ideal sense is only in Eretz Yisrael, and therefore, before we can even begin to speak of any mitzvos, we must first explain our claim to Eretz Yisrael.
I would like to add something to this Kli Chemdah. The Rambam writes that Kiddush hachodesh must be done by the beis din hagadol in Eretz Yisrael (see mitzvos aseh 153 in SH”M). The cheshbon, the calculation that we rely on to determine when to make rosh chodesh and leap years, is not what effects kiddush hachodesh – the cheshbon just serves to reveal (giluy milsa) of what beis din has been mekadesh. The Rambam adds that if theoretically there were no Jews living in Eretz Yisrael (an occurance G-d would never allow to happen), there would be no mechanism for kiddush hachodesh to occur.
How can there be kiddush hachodesh in Eretz Yisrael today without a functioning beis din? R’ Soloveitchik explained (see the essay in Koveitz Shiurei Torah) that beis din hagadol served two functions: 1) they were the supreme judicial body; 2) they served as the representatives of the community of klal yisrael. The power of kiddush hachodesh is invested not in the judicial role of beis din, but in their role as representatives. Today, when we lack their representative role, it is the behavior of the tzibur itself, the observance of the community of Jewish people residing in Eretz Yisrael, which establishes Rosh Chodesh.
Based on this, perhaps one could suggest that Rashi introduces our claim to Eretz Yisrael not just because mitzvah observance in general ideally must take place in the context of Eretz Yisrael, but specifically because the mitzvah of kiddush hachodesh, the first mitzvah of the Torah, the mitzvah which Rashi thought should open the Torah, is possible to fulfill only given the presence of the Jewish people to Eretz Yisrael.