After the Splitting of the Sea, the Torah summarizes: "Israel saw the great hand that Hashem did to Egypt, and the nation believed in Hashem and in Moshe, His servant" (Shemot 14:31). This belief in Moshe was further bolstered at Sinai, where the pasuk says: "I am coming to you in the thickness of the cloud, so that the nation will hear when I speak to you, and they will believe in you as well" (Shemot 19:9). Chazal, commentators, and Jewish philosophers throughout history tried to explain what the element of belief in Moshe was, and how it developed as a result of these events.
Unklelus, in his Targum, as is fitting to his style, was not willing to equate the belief in Hashem that is described with the belief in Moshe. He translates: "They believed in the prophecy of Moshe, His servant." Hadar Zekeinim phrases it somewhat differently: "They believed that Moshe was Hashem’s servant and that everything he did was based on His command." The Ibn Ezra also explains that the belief was in Moshe’s relationship with Hashem.
The Alshich, on the other hand, said that already in Egypt, Bnei Yisrael believed in Moshe’s representation of Hashem. What changed at the Sea was that the multitude of other peoples who followed Bnei Yisrael believed in him.
According to each explanation, what changed further at Sinai? Rashi explains that there people began believing in prophets in general, besides Moshe. In other words, regarding Moshe, there was no need to strengthen belief. Ibn Ezra, though, said that there were many in Israel who believed that a spiritual being could not talk to a corporal being with the latter surviving. The Ramban sharply takes issue with this approach, saying that the offspring of Avraham would not doubt the existence of prophecy. The Ramban says that Moshe’s prophecy was strengthened so that if in some future generation, a "prophet" would say something that contradicted Moshe, Moshe’s word, which the nation witnessed, would prevail.
The Rambam (Yesodei Hatorah 8:1) said that the quality of the belief increased as a result of Sinai. The belief in Moshe was not based on the miracles he performed, for such belief carries some doubt as it can theoretically be performed by magic or sleight of hand. At Sinai, the people saw for themselves that Hashem spoke to Moshe, and therefore they would never come to doubt it.
It is fascinating, although not altogether surprising, that Moshe is viewed by hundreds of millions of people, from different religions, as a leading prophet. Of course, his centrality in Judaism, is at the very core of our belief.