I too have wondered about this. The Microsoft Encarta World English Dictionary 2001, on "corny," says "Late 16th century," in square brackets after the definition. Can the expression be that old? The Shorter Oxford English Dictionary, 5th Edition, says the first such use was 1930-1969, but gives only a definition, not an origin. I've always figured the reference was to farm life, so that a person among the corn would not be in the flow of urban life, thus would be a hayseed -- unsophisticated, not "with it."

As for "cheesy," 1870-1899 is the Shorter OED's first recorded date for its use in that sense. I wonder if it has to do with "cheeseparing," meaning stingy?