Rabbi Yonah H. Geller z"l, stated in my hearing that "only a free nation has a calendar;" (since time belongs to HaShem we were chosen and given the mitzvah to sanctify time;) so the short answer is this is the first Mitzvah HaShem commanded to us (Bnai Yisrael) because it is our beginning of The Nation as a free people.
Because we (Yisrael) are referred to as HaShem's firstborn (Shmoth 4.22), we sanctify time in all places.
Freed from slavery, the Jewish people were presented with a sudden treasure of time. As slaves, their time had been taken from them, but now they had a prophet who got it back. What would they do with this segulah?
When sanctifying the new month, the Beth Din declares, “Mekudash, mekudash! Sanctified, sanctified!” Hashem gave the Jewish people the power to sanctify time by what they say and do, not only to give it worth, but to infuse it with holiness. Rosh Chodesh, the first day of the new month, has the status of a minor festival. Tehillim (Psalms) 81.4 reminds us that we can sanctify the moon's renewal of our lives. By living in a way consistent with Torah, we sanctify our time and preserve it for all eternity. The mitzvah of Rosh Chodesh Nissan delivered the gift of time.
The root used in the Torah is Rosh, meaning head or first as in first born, which is related to rashut.
But before the root, we read "HaChodeesh hazeh lacheem" and the implied meaning is that HaShem set the month of Nissan (spring) before Moshe and Ahron as a choice (Choose you this day life...Deuteronomy 30:15-20).
As sabbahillel points out, "In essence, R' Soloveitchik's comments expand upon the words of the S'forno: HaChodesh Hazeh Lachem - “from this point onwards the months shall be yours to do as you see fit."
Here, Moshe, Ahron and the entire Children of Yisrael are given a leadership role (olam hazeh and olam habah - the present status of things being temporal) as demonstrated by their ability to set apart the month of Nissan as the beginning of months. Since we follow the "correct calendar" (lunar/solar), Pesach always fall in the spring on the day in which HaShem liberated us from slavery.
Rashut (with a kamatz) means "authority". A related term reshut (with a sheva) means permission. (Another term, reshet means net-work as in Shmoth [Exodus] 27:4.) Avshalom Kor [in Yofi Shel Ivrit (chapter 31)] "writes that rashut comes from the word rosh ראש - "head". Klein agrees, and writes that the word is "probably a shortened spelling for rashut with an alef - ראשות"."
The very next commandment after "sanctification of the new moon" is to "draw out and slaughter the god of the Egyptians" before their eyes!
Since we have "authority" to sanctify the new moon; as a public act (Shmoth 12.1-2), we don't need permission for a public act. "In the private domain - only the individual has permission to act, whereas in the public domain the entire public can do as they please." http://www.balashon.com/2007/07/rashut-and-reshut.html