The first appearance of "crottled greeps" seems to be 1953, used by Dean Grennell in a joke one-shot science fiction fanzine called Filler and containing nothing but short filler items -- "Filler 378" is quoted in several places as:
"But if you don't like crottled greeps, what did you order them for?"
Apparently, the origin of the words in the phrase is from the cartooning term "crottles," used to describe the little bubbles and lines drawn above a cartoon character's head to indicate that they are intoxicated; and an English-speaker's spelling of the French word "grippe," used in French and in the past also in English for the disease now called "influenza." In 1956, Lee Hoffman used the name to describe a "seductive but lethal viand" in a short story in another fanzine, Grue (issue #27). Many other stories used the phrase as a fun reference for dedicated fans to catch, and and at least one filksong. None of the stories until the 1990s really specified what, exactly, crottled greeps were. People's suggestions include:

In 1990, Greg Costikyan's "Another Day, Another Dungeon," took the running joke of no one knowing what crottled greeps were and ran with it; a fan review notes "Every time the characters stop for food, the food vendor tries to sell them greeps. The vendor would tell them his life story, complete with the story of the greeps. Strangely enough, every single vendor had a completely different species of greep. There were bird greeps, fish greeps, insect greeps, small furry greeps, and more." Apparently, though, the greeps weren't all served crottled.

In 1993, The Gripping Hand by Larry Niven and Jerry Pournelle topped the many fannish speculations by making the crottled greeps ordered by one brave traveler turn out to be live food:

The creatures in the bowl might have been four-legged crabs. Their sides pulsed. Renner remembered reading that they were land creatures. They could almost reach the rim before they dropped back. Their eyes were locked on Renner's as they climbed toward him. They looked hungry and determined.
"Pick up the crottling fork," Belinda whispered. "The two-pronged fork. Use your thumb and two fingers."
It was sitting beside the bowl. Renner picked it up. Belinda whispered, "Stab just behind the head plate. Do it hard enough to set the prongs. You don't want it to drop off."
Hesitating was bad: the greeps would move. You couldn't blame them. Renner stabbed one and lifted the fork. Belinda said, "Scrape it off on the edge. You didn't stab hard enough. They bite."
Renner scraped it off and tried another. The beasts weren't fast, but it wasn't easy to center the fork. He stabbed.
"Good. Pick it up. Your left hand takes the tail. Pull hard."
Renner pulled. The exoskeletal tail came right off, exposing two inches of pale meat.

Sources:
http://fancyclopedia.wikidot.com/crottled-greeps
http://www.urbandictionary.com/define.php?term=crottled+greeps
http://forums.comicgenesis.com/viewtopic.php?t=19854&highlight=&sid=345ce99a0c49cbf139690d4f9dbe03b5___1.htm
Niven, Larry, and Jerry Pournelle. The Gripping Hand. New York: Pocket Books, 1993. https://books.google.com/books?id=YGALosQ3-DYC&pg=PA27&lpg=PA27&dq=crottled+greeps+gripping+hand