This is שבת שירה, and after the splitting of the sea, the Torah says that the people believed in Moshe:
ל ויושע ה׳ ביום ההוא את ישראל מיד מצרים; וירא ישראל את מצרים מת על שפת הים׃
לא וירא ישראל את היד הגדלה אשר עשה ה׳ במצרים וייראו העם את ה׳; ויאמינו בה׳ ובמשה עבדו׃
The question is, what did they believe? They believed him when he first came to them:
ל וידבר אהרן את כל הדברים אשר דבר ה׳ אל משה; ויעש האתת לעיני העם׃
לא ויאמן העם; וישמעו כי פקד ה׳ את בני ישראל וכי ראה את ענים ויקדו וישתחוו׃
And they believed him at מעמד הר סיני:
ויאמר ה׳ אל משה הנה אנכי בא אליך בעב הענן בעבור ישמע העם בדברי עמך וגם בך יאמינו לעולם; ויגד משה את דברי העם אל ה׳׃
We understand the difference between the latter two “אמונות”. They represent two levels of faith in Moshe’s prophecy. When he first came to Egypt, he did אותות to convince the people that ה׳ had sent him:
הנביא, אפשר שתהיה נבואתו לעצמו בלבד, להרחיב ליבו ולהוסיף דעתו, עד שיידע מה שלא היה יודע, מאותן הדברים הגדולים. ואפשר שישולח לעם מעמי הארץ, או לאנשי עיר או ממלכה, לבונן אותם ולהודיעם מה יעשו, או למנוע אותם ממעשים הרעים שבידיהם; וכשמשלחין אותו, נותנין לו אות ומופת כדי שיידעו העם שהא־ל שילחו באמת.
But faith in a נביא only applies to that generation (a נביא cannot establish a law that lasts, but only a הוראת שעה). Moshe, at מעמד הר סיני, was stronger than that.
א משה רבנו—לא האמינו בו ישראל, מפני האותות שעשה…
ב ובמה האמינו בו, במעמד הר סיניי: שעינינו ראו, ולא זר, ואוזנינו שמעו, ולא אחר—האש והקולות והלפידים. והוא ניגש אל הערפל, והקול מדבר אליו; ואנו שומעים: משה, משה—לך אמור להם כך וכך…
ג ומניין שבמעמד הר סיניי לבדו, היא הראיה לנבואתו שהיא אמת שאין בו דופי—שנאמר (שמות יט:ט) ”…בעבור ישמע העם בדברי עימך, וגם בך יאמינו לעולם“: מכלל שקודם דבר זה, לא האמינו בו נאמנות שהיא עומדת לעולם, אלא נאמנות שיש אחריה הרהור ומחשבה.
But what was this apparent intermediate stage, of ויאמינו בה׳ ובמשה עבדו? Rav Hutner summarizes the problem:
…נמצינו למדים כי אמונת ישראל במשה באה בשתי מדרגות. בתחלת נבואתו על ידי אות ומופת כדרך שנקבע לדורות בהלכות נבואה. אלא שזה היה רק לשעה עד שעמדו על ההר. שמשעת העמידה על ההר ישראל עצמם הם עדים על נבואתו. ואם כן צריך לברר מה היא טיבה של חידוש אמונה במשה המבוארת כאן בשעת קריעת ים סוף. הרי גדר אות או מופת היה גם מקודם וגדר עדות עדי לא היה…ומבואר דבשעת היציאה נמצא חידוש באמונת נבואתו של משה…וצריך באור חידוש זה מה הוא.
Rav Hutner proposes that this intermediate stage is related to another role of Moshe, one that does not appear to be related to אמונה at all.
ואין עושין סנהדראות [לשבטים, אלא על פי בית דין של שבעים ואחד]: מנא לן? כדאשכחן במשה דאוקי סנהדראות ומשה במקום שבעים וחד קאי.
דאוקי סנהדראות: בעצת יתרו ומשה היה שופט ודיין על פי הדבור ושקול כסנהדרי גדולה שבירושלים.
ומבואר, איפוא, דמשום שמשה היה דיין על פי הדבור, ודבר זה לא מצינו לו דוגמא בנביא אחר, ממילא מחמת זה עצמו היה לו למשה חלות שם סנהדרי גדולה. ומעתה יש לדון באימה דמדרגה זו של משה דבמקום שבעים וחד קאי התחלתה היא משעת קידוש החדש אשר במאמר ”החדש הזה לכם ראש חדשים“. שהרי קידוש החדש הוא מעשה בית דין…ומשה קידש את החדש על פי הדבור. וכל שעושה מעשה בית דין על פי הדבור יש לו מדרגה זו של במקום שבעים וחד קאי.
What does the בית דין הגדול mean, in the context of קידוש החודש? My son-in-law, Rabbi Aron Rubin, gave a shiur last week about that, and said that Rav Soloveitchik explained that the Sanhedrin has two roles. One, to be the supreme court of the nation. The other is to represent the will of the nation, and it is in this aspect that they are acting in קידוש החודש.
Kiddush HaChodesh is entrusted to the nation of Israel collectively, and the members of the Beis Din act as agents of the people as a whole. The function of Beis Din in Kiddush Hachodesh is independent of its judicial and legislative functions. The public announcement of Rosh Chodesh is a symbolic enactment of Kiddush Hachodesh by Beis Din on behalf of the nation of Israel. The words recited during [Birchas] Hachodesh, חברים כל ישראל, symbolize the collectivity of Israel, whom the Beis Din represents.
So Moshe achieved the status of “sanhedrin” when he was given the laws of קידוש החודש; he was the representative of the nation as a whole. But that was well before קריעת ים סוף, and not dependent on ויאמינו…במשה at all.
The אמונה that בני ישראל had at קריעת ים סוף was in במשה עבדו. What is the significance of being an עבד?
ושוב מעשה ברבי חנינא בן דוסא שהלך ללמוד תורה אצל רבי יוחנן בן זכאי, וחלה בנו של רבי יוחנן בן זכאי. אמר לו: חנינא בני, בקש עליו רחמים ויחיה. הניח ראשו בין ברכיו ובקש עליו רחמים, וחיה. אמר רבי יוחנן בן זכאי: אלמלי הטיח בן זכאי את ראשו בין ברכיו כל היום כולו—לא היו משגיחים עליו. אמרה לו אשתו: וכי חנינא גדול ממך? אמר לה: לאו, אלא הוא דומה כעבד לפני המלך, ואני דומה כשר לפני המלך.
כעבד: בן בית נכנס ויוצא שלא ברשות.
So ויאמינו בה׳ ובמשה עבדו meant that בני ישראל believed that Moshe could speak to ה׳ at any time, and ה׳ would listen, and that Moshe represented them, the people as a whole. He stood in the place of the בית דין הגדול, and the בית דין הגדול stood in the place of the עם.
ים סוף was the first time the people asked Moshe to intercede with ה׳ for them. When the sea split, they understood that this intercession was possible.
When Moshe did the signs, back in פרשת שמות, בני ישראל believed that G-d spoke to him. At ים סוף, they believed that he could (and would) speak to G-d on their behalf. Both were necessary for Moshe to achieve that next level, of bringing the Torah to the people.
ג ומשה עלה אל האלקים; ויקרא אליו ה׳ מן ההר לאמר כה תאמר לבית יעקב ותגיד לבני ישראל׃ …ח ויענו כל העם יחדו ויאמרו כל אשר דבר ה׳ נעשה; וישב משה את דברי העם אל ה׳׃