The four parshios of Shekalim, Zachor, Parah, and HaChodesh all represent events that normally occur at this time of year, and are similar to the "inyana d'yoma" leining that we read on yom tov. Shekalim had to be brought at this time of the year, Zachor presents a framework for Purim, and Parah commemorates the fact that all of Klal Yisroel had to purify themselves, for everyone was obligated to partake in the korbon Pesach. Parshas HaChodesh, however, does not fit this pattern. It is true that they had to be mekadesh the month of Nissan, but not any more so than other months; Pesach needed a specific calendar date, but so does Rosh Hashana, Yom Kippur and Succos. HaChodesh does not seem to be more inyana d'yoma now than at other times. It is also true that the mitzvah of kiddush hachodesh was first given at the time of Pesach, but there doesn't seem to be a particular reason for this. So why is Parshas HaChodesh included in this series?
In order to understand this, we need appreciate the depth of the miracle of Pesach. We tend to focus on Pharoh, his power, and his control of the Jewish people, Hashem in turn overpowering him, etc. But the real problem was much deeper. Klal Yisroel just about did not exist!
Chazal comment on the verse "or has G-d ever taken a 'nation from within a nation', that it is like a shepherd taking a fetus from the womb of a mother." The Maharal explains that Klal Yisroel was in a fetal stage. To the naked eye they appeared to be part and parcel of the Egyptian people. They themselves were not yet fully conscious of being a nation. They had come down to Mitzrayim as a family, and had become embedded therein. We speak of how terrible assimilation is, but this was a "pre-assimilation"- they had yet to really exist. They were a potential people, but not an actualized nation. This is why Hashem taking a "nation from within a nation" was an extraordinary act.
The mitzvah of kiddush hachodesh, represents an extraordinary power given over to Klal Yisroel, and that is the "power to renew". Chodesh-month and chadash-new share the same root, for the month is the cycle of constant renewal in the world, each month being a "renewal" of the waning moon. Furthermore, the one aspect of nature that imprisons us is time. We are the product of what was. Therefore, genuine chiddush and total change seem well-nigh impossible.
Not only was the act of "creating" a people performed by Hashem, but He also gave us that same ability. We now have the power to recreate ourselves anew. It is akin to being able to lift ourselves by our bootstraps. It is an extraordinary power, and it means that in fact, no matter how far we sink, as long as we are "Yisroel" we can recast ourselves even out of seeming nothingness!
The gemara actually makes a point - seemingly for technical halachic reasons - that the moon totally disappears for a few hours, in a way that it is impossible to see at all. This means that the event of renewal of the month happens out of a seeming void, which was exactly the state of affairs in Mitzrayim.
So, although kiddush hachodesh is halachically relevant every month, its true essence is both needed and expressed in the month of Pesach. The seed of the aavos had disappeared for two centuries from the horizon, and reappeared from seeming nothingness. This gift of renewal has now been endowed to Klal Yisroel.