Tina and I dove this area of Irian Jaya years ago. It was beautiful and very wild. We didn't see any fin-walking horn sharks, though. (We did see a species of stonefish that is classified as deadly and the locals were like: "Oh, if you get stung, you chew that leaf over there, spit it into the wound, and you're fine.")
Oh, and I had to pin a cassowary that had escaped to the bottom of our boat for 2 hours. They named him "Larry the Cassowary" in honor of the occasion. He was a lot of fun (I mean, after the boat ride was over and he was released on the island and calmed down). He would chase after you and then you could spin around and chase him. It was sort of like having a small T. Rex as a pet.