‘... three too many’ (1678)
One of the earliest versions of “two is company, three is a crowd” was recorded in 1678 by John Ray, in his collection English Proverbs, p.471
One's too few, three too many
Therefore, presumably, ‘two’ was then considered idyllic.
The Oxford Dictionary of Word Origins claims that the original proverb is from 1730s, and cites an English translation from The Spanish and English Dictionary by J. Stevens, printed in 1726.
Prov. Compañía de tres no vale res;
A company consisting of three is worth nothing.
It is the Spanish opinion who say that to keep a secret three are too many, and to be merry they are too few.
John Collins provides this translation which resembles more closely the English proverb (1834)
“Three persons in company are too many for any secret affair, and two few for social enjoyment.”
‘... three is none’ (1840)
From The Facts on File Dictionary of Proverbs by Martin H. Manser (link), we learn the following:
The proverb was first recorded in the mid-19th century, in the form “Two is company but three is none,” (W.C. Hazlitt, English Proverbs ) but the sentiment it expresses is of earlier origin.
Variants of this proverb: two is company but three is none; two's a couple, but three's a crowd, four's too many, and fives's not allowed.
Henry Downes Miles' Dick Turpin, printed in 1840, contains the following adage
Their conversation had proceeded thus far, and Dennis appeared about to offer his services in some other shape, when Esther appeared slowly advancing towards them.
“Two is good company when three is none”
Five years later, we have this detailed analysis in The Usurer. A Tale of Marseilles. written by Percy B. St. John.
“Two is company—three is none:” so says the adage; but, as is often the case, the adage is in error. There are occasions when certainly nothing can be more delightful than for two people, of course of different sexes, to find themselves alone, and interchange all those sweet vows and soft nothings which make up the sum-total of a declaration and an acceptance. But still, three is often a better number for enjoyment far than two. Even a pair of levers are more at their ease—especially if the one who is generally considered de trop is a talkative and companionable person
‘... three is trumpery’ (1866)
Yet another variant appeared in the late 19th century containing the term, trumpery, i.e., something showy but worthless.
An old rhyme Molly had heard -Betty use would keep running in her head and making her uneasy-— “Two is company, Three is trumpery.”
Wives and daughters, an Every-Day Story By Elizabeth Gaskell
‘... three's a crowd’ (1870)
As for the more modern version containing the term “three's a crowd” it appears to be American. The earliest instance I found is from Delaware Gazette. December 02, 1870, the article is titled Miss Althea's Rubbers
I had my reward when Steven lifted me down at our gate, and she said :
"You're your mother's own gal ! You hain't never let me feel that two's a company and three's a crowd !" Steven had walked up the long path with me to carry my shawl, and might have said just a word then—a woman can live long on only a word, if it be loving enough—but he almost threw the shawl across my arm, and ran down the
path as if he were glad to be well rid of me.
As I "piled Ossa on Pelion" in my thoughts against the possibility of his
loving me as I desired to be loved, the forenoon wore away, and the apples
‘... three are a crowd’ (1872)
Courtesy of @Sven Yargs are the following two excerpts: “One of My Bygones,” in the Wichita [Kansas] City Eagle (November 21, 1872). It's also worth mentioning that the saying contains the plural verb:
“My dear turtle-doves.” she said at last, laying one hand on mine and looking hard at my friend. “I see how it is with you. You have reached the point where ‘two are a company and three are a crowd.’”
And from an item titled "Proverbs" in the Juniata [Pennsylvania] Sentinel and Republican January 21, 1874. Here the verb is singular and in the simple past.
Now go and ask a couple of doting lovers if they believe in that sort of thing ["the more the merrier"]. They would undoubtedly think that two was company, and three was a crowd. One thing is certain it is hard, very hard to crowd that idea into the heads of some that is or that was to be mother-in-laws
P.S Many thanks to Sven Yargs who provided the last two links.