I think that Jesus's followers, being the Jews they were, would look at how Jesus's theology fits with the Torah. When Christ says "water and the Spirit," the first thing that pops in my head is Genesis (John's Gospel is like Genesis part II):
In the beginning God created the heavens and the earth. The earth was without form, and void; and darkness was on the face of the deep. And the Spirit of God was hovering over the face of the waters.
The last sentence, "the Spirit of God was hovering over the face of the waters," is one of the Torah passages I think Christ has in mind here. The world was created in water and Spirit, and must be reborn in water and Spirit.
The next thing that pops into my head is Noah's ark (which St. Peter in his first letter points out).
And the dove came back to him in the evening, and behold, in her mouth was a freshly plucked olive leaf. So Noah knew that the waters had subsided from the earth.
I connect this to Jesus's Baptism:
When He had been baptized, Jesus came up immediately from the water; and behold, the heavens were opened to Him, and He saw the Spirit of God descending like a dove and alighting upon Him. And suddenly a voice came from heaven, saying, “This is My beloved Son, in whom I am well pleased.”
The floodwaters of Baptism and the Spirit in the form of the Dove cause the world to be reborn. And this is very important, because before Creation can be born again, the Word Himself must be reborn. The Word was born eternally as Son of the the Father, and reborn as Son of Mary. His rebirth leads to the rebirth of the rest of creation (this is straight from St Leo the Great's Tomb, btw).
The Exodus comes to mind next:
Then Moses stretched out his hand over the sea; and the Lord caused the sea to go back by a strong east wind all that night, and made the sea into dry land, and the waters were divided. So the children of Israel went into the midst of the sea on the dry ground, and the waters were a wall to them on their right hand and on their left. And the Egyptians pursued and went after them into the midst of the sea, all Pharaoh’s horses, his chariots, and his horsemen.
Israel was saved from slavery in Egypt by seawater and a strong east wind. Now, "spirit" is Latin for breath. The connection between wind and breath are obvious. The new Israel is saved from slavery in sin by water and the Spirit.