I imagine that most of the "Tasty surprise inside" type of foods were discovered somewhat by accident and/or observation - a coconut dropped on a rock or a pineapple broken open with a stick; certain species of coastal fowl are quite adept at opening clams or mussels by dropping them on rocky shores.
No doubt, the "creative culinary insight" was urged along, in no small way, by the instinct to survive. As previously stated, starvation is a powerful motivator. When your stomach becomes "closer than a speakin' aquaintance with your backbone", your definition of "tasty" changes radically.
Bearing that in mind, I still think it took alot of balls to consider crabs, lobster, octopus, and squid as dinner candidates . . .
Observation (and experience) would tell you that milk from mammels was probably OK to consume. And since one rapidly aquires a "waste not, want not" mindset under the pressure of survival, learning to utilize "spoiled" dairy products and develop preservation methods for other foods makes pretty good sense.
I understand the Vietnamese have a little dish called "nuc maum" (sp?) that is mainly vegetables and eggs mixed in a sealed clay pot and buried for a few months to ferment. Reputedly high in nutritional value, but definately an aquired taste.
Recipes for head cheese, scrapple, pigs feet, tripe, blood pie and sausage were all driven by the desire (and need) to make every possible use of slaughtered livestock - whatever can't be worn or used as a tool is food; and helps decide who makes it through a hard winter. Personally, I suspect a taste for mountain oysters was the result of an "I double-dog dare ya" exchange . . .
My father had an obvious appreciation for good food, but I noticed while growing up that he ate even poorly prepared meals with evident gusto. Eventually, when I commented on that to him, he explained that when he had been captured by German troops during the Ardennes offensive, the German supply situation was so disrupted by Allied air superiority that there was little, if anything to feed the POW's. Their guards didn't fare much better. It was an exceptionally bad winter, further complicated by the need to constantly move the POW's in retreat of the rapid Allied advance. When encamped, the guards would let POW's dig in the frozen fields for potatoes and turnips. My father said he saw men who were the best of friends - repeatedly risking their lives for each other - willing to kill each other over a handful of rotten, frozen cabbage. He said the experience gave him "perspective, and gratitude".
Then again, he also gave me this gem:
Everything tastes like chicken (more or less) . . .