A new species of walking epaulette sharks (Hemiscyillum freycineti) has been discovered off the coast of Indonesia. These sharks actually walk using their pectoral fins. Take time out for a dive alongside this shark and see some other amazing ocean wildlife in this diver's video:
Video Source: Conservation International.
As if walking is not interesting enough, another species of epaulette sharks (Hemiscyllium ocellatum) are actually resistant to hypoxia (low oxygen), which is important if you are living in an environment wherein the oxygen concentrations can vary dramatically (Wise et al., J Exp Zool 281:1-5, 1998).
In deep waters off the coast of Japan, walking fish have also been observed alongside huge dead-man's crabs that are known for eating corpses in this video from National Geographic...spooky...