As Thomas Paine pointed out in The Age of Reason, Alexander the Great was also claimed to have divine help in parting a sea. In book 2 of Antiquity of the Jews, Jospehus says that the Sea of Pamphylia (now know as the gulf of Antalya in what is now southern Turkey) was parted for Alexander on his way to conquering Persia. He cites four sources for this. Strabo said it was good fortune, but Callisthenes, Arrian, and Appian specifically said that it was divine providence. Callisthenes' account was said to be first hand, as he accompanied Alexander on this expedition, though it came to Jospehus second-hand through the writing of Eustathius who cited Callisthenes writings.
This is interesting for a couple reasons. One, there is more evidence for the parting of the Pamphylian Sea than of the Red Sea. Secondly, as Paine pointed out, if Christians are going to accept Josephus' account of Jesus as evidence for Jesus, they also must accept the account of the parting of the Pamphylian Sea for Alexander. Alexander, of course, believed in the pagan Greek gods (and some historians have even speculated that he believed himself to be divine), so this presents a problem for Christians. Of course, most will probably just ignore it or dismiss it.
http://www.sacred-texts.com/jud/josephus/ant-2.htm (see chapter 16, part 5)