I don't know which was made first, but I think that the "Sullivan" version was first since the clam (with his eyes changed to beady black ones) appears in the Sesame version. The Sesame version was less funny, but a bit more elaborate in that it was filmed with shots of real fish. The Sesame version featured four puppets: the scuba diver, a fat blue fish, a clam, and an octopus (I don't know if it's an AM or not). The "Sullivan" version featured an orange scuba diver, a green octopus with a moustache, a clam w/ sleepy eyelids, and a gigantic clam.
The Sesame version also had a bit of an educational value (of course), counting the octopus's legs.