I have heard that there is a Midrash which says that Dolphins swam on either side of the dry land when the sea was split for Moshe to warn the fish not to swim out onto dry land. Why are there dolphins in the sea in the first place, they do not naturally live there? Does the Mirdrash address this question?
To add to Gershon's answer, it could have come from the fact that Tachash (an animal used for its skins in the Mishkan) is often translated as a dolphin. Where would Bnei Yisrael have gotten dolphin skins? Why, from crossing the sea, of course! (Note, that is not my question/answer, but one that I've seen ridiculed online.) It's conceivable that this is, in fact, based on some Midrash, but I haven't ever heard it.
There is no such Medrash, this is a fable. Cut and paste to see this link. pn.b5z.net/i/u/6147132/i/A_Tale_of_A_Tail.doc
The website redsea-divingsafari.org mentions that there are dolphins living in the red sea, however as I mentioned above there is no such Medrash, this is a fable.
There are various sites in the southern Red Sea where Dolphins congregate or live. Sammadai national park and Satayah reef are the most well known and both sites are home to spinner dolphins. It is very common to spot these beautiful creatures roaming about the sea anywhere in the south. They are usually very playful and will approach closely so long as you stay calm and respect the dolphins space.