Just because the word "rishon" appears in the context of lulav does not mean there is a connection with every other place the word "rishon" appears -- it's not a word game that the Midrash is playing. What Chazal are telling us is that the geulah, i.e. the defeat of Eisav, the building of Mikdash, the coming of Moshiach, all hinted at by that word "rishon," is already latent and part and parcel of the mitzvah of 4 minim on Sukkos. You want to taste the geulah and know what it is all about? Pick up a lulav and esrog.
Perhaps this is why Chazal tell us (Avodah Zarah 3) that when the geulah comes and the nations will complain that they want another chance to earn redemption as well, Hashem will challenge them to fulfill the mitzvah of sukkah. Why this mitzvah and no other? Because if you can celebrate Sukkos properly, if you can experience the mini-geulah of this chag, then you have proven yourself worthy of geulah on a greater scale. But if you kick the sukkah and are disgusted by it, as the nations reacted, then certainly you don't deserve geulah on a greater scale.
What does it mean that Hashem appears to us "rishon?" The Shem m'Shmuel explains that Chazal discuss a "machlokes" between Bnei Yisrael and Hashem: Hashem asks of us, "Shuvu alai v'ashuva aleichem...," that we take the first step towards teshuvah and he will respond; we ask of Hashem, "Hashiveinu Hashem eilecha v'nashuva...," that Hashem take the first step to bring us closer to him and then we will respond. On Sukkos Hashem breaks the standoff. All we need to do is take a lulav and esrog and Hashem says, "I'll be the rishon -- I'll make the first move and help you come back."
But the mitzvah is not really only about taking a lulav and esrog. "U'lekachtem lachem..." explains the Chiddushei HaR"IM means you have to take "lachem", take yourselves, i.e. pick yourselves up from where you were and be willing to move. We move into the sukkah, we move around the lulav and esrog, and hopefully we will be moved a little bit as well.