That’s a bit beside the question at hand, but in regard to the parting of the red sea, that would only apply if you understand unchanging to mean always doing the same thing and believed God to be within the Universe as opposed to being transcendent.
Concerning the immutability of God, the Bible says something very strange, at least to one of your understanding. Hebrews says: “Jesus Christ is the same yesterday, and today, and for ever.” How very odd, surely, you must think. For, this Jesus Christ he is speaking of not only was born, grew from a babe to a young child, from a young child to an adolescent, from an adolescent to an adult, and then not only moved from working with his father as a carpenter to teaching but, eventually, this Jesus Christ also died. So, clearly, this is a statement that does not mean He did the same thing all the time. In this example, it does not even mean that He was unaffected by time, for clearly Jesus acted within history. So, what then does this mean?
The Bible also says that God is Love. But what is love, and what does it mean for One to be it? Love means to will good for the other. How then, can one be love if one is not dynamic and consistently willing this good? If one is Love, then surely this means that one cannot be static, as love is action to that which is good, which of course would change to a changing world. One would not treat a hardened criminal the same as a child. So then, could it be this, God being Love and Justice, that does not change, over the idea that any specific action cannot be changed to a different one, even though it would be an action within time and creation to a timeless God?