I think that Josh61 is on the right track with the idea that "Go suck an egg" may have begun as a dismissive insult back-formed from the adjective suck-egg. Here is the entry for suck-egg in Harold Wentworth, American Dialect Dictionary (1944):
suck-egg, adj. Egg-sucking ; hence, & usu. mean, base; — used attrib. esp. in 'suck-egg dog' &, less often, 'suck-egg mule.'
[Relevant examples:] 1892 K[entuck]y. He is as mean as a suck-egg dog. 1906 n.w. Ark[ansas]. Cf. 'mean enough to suck eggs,' used both of dogs & men. 1908 e. Ala[bama], w. G[eorgi]a. 'Suck-egg dog.' Common. 1930 e.cent. S[outh] C[arolina]. suck-egg dog = the apotheosis of meanness. 1934 suck-egg n., adj. applied contemptuously 1936, 1938 n.e. K[entuck]y. If it ain't I'm a suck-egg mule. [and] If that is right I'm a suck-egg mule! 1942 Ind[iana]. 'I'll be a suck-egg mule!' Said in disgust.
Harold Wentworth & Stuart Flexner, Dictionary of American Slang, first edition (1960) has this entry for egg-sucker:
egg-sucker n. One who seeks advancement through flattery, rather than work; a "weasel."
But it may be less relevant to the emergence of "Go suck an egg" than the more literal egg-sucking tendencies of some dogs and humans.
Early occurrences of the phrase 'Go suck an egg'
Google Books search results find examples of "Go suck an egg" and "Go suck eggs" dating back to the late 1930s. From Edwin Corle, Burro Alley (1938) [combined snippets]:
"Want somethin', Mr. Mond?" asked Porfirio.
"What I want your junk for?" asked Mond. "Go suck an egg. I carry my own liquor." He pulled a half pint of whiskey from his hip pocket and put it on the table. It was called "Red Boy" and the price on the bottle was thirty-nine cents.
From Advertising & Selling, volume 40 (1947) [combined snippets]:
One man's opinion
In this group — which runs pretty much the same ad indefinitely — might fall the Cozy Couple Under Glass, Golden Wedding. "He has no peers for Fifty Years!" Well, that's one man's opinion . . . and go suck eggs, you old FTC, you. Here, too, we find the red- coated Hunter suspended in midair. Still "First Over the Bars," the man says.
From The Saturday Evening Post, volume 223 (1950) [combined snippets]:
"Anyway," Roy said, "ain't no huntin' allowed on this place, so you better go someplace else."
"Who says so?" the big man demanded, frowning at them.
"Paw says so."
"Well, you tell your paw to go suck an egg."
From Illinois Technograph, volume 72 (1956) [combined snippets]:
"Oh no," cried Oliver, "I want you to help me."
"Go suck an egg, sonny."
Oliver became frantic. After so main failures he was not going to let this one get away. "The book says you have to help me. I summoned you and I'm your master and you have to ..."
From Hollis Summers, The Weather of February (1957) [snippet]:
Andy said why didn't I curl up on the hood and take a nap, and I told him to go suck an egg. We were sour all right.
Most of these examples have a distinctly countrified or lower-class tone to them, except perhaps for the one from Advertising & Selling, which has a coarse bravura of its own.
Antecedents of 'Go suck an egg'
A possible source of the insulting invitation to "Go suck eggs" is suggested in Seawell v. Carolina Central Railroad Co. (Supreme Court of North Carolina, June 1903):
[Ramseur and Carroll, agents of the defendant railroad], together with other persons to the plaintiff unknown, wrongfully and unlawfully did assault and beat the plaintiff, striking him on the face and on various other parts of his person with eggs, and did otherwise maltreat the plaintiff, and in the presence of the plaintiff and of various other persons did use indecent, insulting and opprobious language with reference to the plaintiff while at said station, by reason of which assault, battery and maltreatment the plaintiff was obliged to ride on said train ... in clothing which was badly soiled by the impact and bursting of said eggs, and thereby rendered uncomfortable, disagreeable, and for the time unfit for use on said train ...
...
There was also evidence that Thrower, the conductor, was within fifteen or twenty feet of the plaintiff, and offered him no protection; that no other agent or employee of the defendant [company] offered him any protection; that Ramseur and Carroll were in the crowd on the platform, when some one in the crowd said: "Leave here, you Populist dog, you suck eggs. I see them on you," the whole crowd laughed and jeered, Hamrick [not previously identified] calling out, "Put that suck-egg dog off at Buffalo, and let him wash himself," ...
The distance between doesn't seem terribly far from telling someone as an insult "You suck eggs" and telling someone derisively "Go suck eggs [or an egg]" doesn't seem terribly far.
Another interesting phrase from the late 1800s is the taunt apparently current in the nineteenth-century United States among boys, "I dare you to do X, and anyone who will take a dare will suck eggs," often followed up with "and anyone who will suck eggs will steal a sheep." One version of this taunt appears in Mark Twain, The Adventures of Tom Sawyer (1876):
Smarty! You think you're some, now, don't you? Oh, what a hat!"
"You can lump that hat if you don't like it. I dare you to knock it off—and anybody that'll take a dare will suck eggs."
"You're a liar!"
"You're another."
...
Tom drew a line in the dust with his big toe, and said:
"I dare you to step over that, and I'll lick you till you can't stand up. Anybody that'll take a dare will steal sheep."
Another appears in Samuel Adams, "The Realm of Enchantment," in McClure's Magazine (September 1904):
"I dare you. I black-dog dare you."
“Any boy 'at 'll take a dare 'll suck eggs, and any boy 'at 'll suck eggs 'll steal sheep,” quoted the other in a solemn chant.
Evidently, something about sucking eggs is notoriously revolting to the youthful mind and inexcusable in a farm dog's conduct. This vividness of these impressions seems to have led to its becoming a metaphor for shameful human misconduct—quite apart from the odd and seemingly unrelated proverb "Don't try to teach your grandmother to suck eggs"—as the following epigraph to the January 1908 issue of The Philistine: A Periodical of Protest suggests:
All good men suck eggs, but those who are wise hide the shells.—Ali Baba