When I consider this question I consider what exactly Christ did while He lived. The atoning sacrifice was essential in order to redeem mankind. But the Catholic Church distinguished between redemption and salvation. Christ redeemed mankind, the family as a whole, but saves individuals each. The atoning sacrifice was accomplished once and for all at Calvary. But that’s not all there is to the story.
What else did Christ do, while he lived? He established the Church. Why? It would be the mechanism by which he draws all men to Himself. It is His body, holding infallible authority to teach, holding sacramental rites to bring about life in each of us. And it is through this Church that Christ accomplishes the act of salvation. That is, we are saved through the Church, who is Christ.
So the question becomes: would it have been possible to establish the Church, as it was needed to be, immediately after the fall? My answer is no. The whole history of man prior to Christ occurred in preparation for Him and the Kingdom He would establish. This doesn’t merely include the history of the Semitic people, to whom the Divine Law of God was given, and whose kingdom, the kingdom of David, would be the model of Christ’s Kingdom, but also the whole history of myth that grew up in the various cultures around the world that find their fulfillment in Christ, and the various other sets of truths found in other religious systems that were ignored in Judaism in favor of strict adherance to the Law, which have since been exemplified in the truth of the Church.
I can’t imagine that this mechanism of the Church that is necessary for the salvation of all could have been properly established immediately after the fall. Sometimes, time must ripen before certain things can be done.