This quotation is found in Part two of the poem and refers to some sort of sea creatures that have become prominent/visible in the sea. The supernatural nature of the Mariner's experience is illustrated in this part also indicating that there seems to be no "Beautiful" creatures in the sea. Thus lies the challenge for the Mariner: to find beauty amidst the "rot."
Part II of the poem reveals the ill effects of the curse that have come upon the ship because of the cruel and thoughtless act of the "ancient mariner" in killing the albatross with his cross bow. The ship drifts into a region where no breeze blows and remains there for several days. Consequently, the entire ship and its crew were scorched by the hot sun. Their supply of fresh water was soon exhausted. It became so hot that the wooden boards of the ship began to shrink and the salty sea water around the ship began to evaporate so fast that it seemed as though the entire sea had begun to rot and stink. The "ancient mariner" remarks that the situation became so grim that the level of the sea water had fallen so low because of the rapid rate of evaporation that he was able to see the deep sea creatures crawling and slithering about on the sea floor. The sea itself had become "slimy"-muddy, because of the low level of the sea water as a result of the unrelenting heat of the sun: "The very deep did rot: O Christ!/That ever this should be!/Yea, slimy things did crawl with legs/Upon the slimy sea."
In those days, no one had dived deep into the bottom of the sea and this reference by Coleridge to "slimy creatures" at the bottom of the sea is meant to heighten the element of mystery in the poem.