John Ayto, Oxford Dictionary of English Idioms, third edition (2009) has this entry regarding the sense of the expression:
a dose (or taste) of of your own medicine the same bad treatment that you have given to others. The idea of taking or receiving your own medicine has been in metaphorical use since the mid 19th century.
During the nineteenth century, medicines often tasted quite horrible, and many were of dubious efficacy (if not downright harmful) to the patient. Under those circumstances, the idea of "receiving what you prescribe for others" may be understood as similar in sense to such folk expressions as "what's sauce for the goose is sauce for the gander" and "turnabout is fair play."
The first Google Books search match for "a dose of [one's] own medicine" is from 1835; the earliest match for "a taste of [one's] own medicine" is from 1866 (although the Library of Congress newspaper database finds an example from 1859). The examples that follow are drawn from both Google Nooks matches and Library of Congress newspaper database matches.
'A dose of [one's] own medicine]'
Here are some early instances of this form of the expression. From William Leggett, "Brought to the Gangway," in The New York Mirror: A Weekly Gazette of Literature and the Fine Arts (April 19, 1834), in a scene in which a naval lieutenant is ordering the flogging of a sailor:
"So, so! worse and worse—from insolence to mutiny! A mere dislocation at first—now a compound fracture. Hurry along here, boatswain's-mate, and proceed to this young gentleman's extremity — come, sir, you had better step quicker, or you may chance to get a dose of your own medicine."
From the New York Daily Tribune (November 5, 1842):
Well Pleb. [that is, The Plebeian, a rival newspaper] why don't you take a dose of your own medicine, and publish and advocate the "regular candidates" nominated at Tammany Hall? Why is your Assembly Ticket dropped? Why are you and all the prominent wire-workers now engaged in machinations to defeat one of the "regular candidates?" So long as the rule works in favor of the packed candidates, you "go it with a perfect looseness," but when it happens to favor the Working Men, you repudiate your own doctrines and unite to defeat the "regular candidates."
From "Chance for Another War!" in the [Brattleboro,] Vermont Phœnix (August 19, 1847):
If rapine and butchery are the right methods for a civilized, Christian nation to seek redress for unpaid debts—as many who have named the name of the "Prince of Peace" pretend—would not the gigantic swindling operations of certain Locofoco States [states dominated by a faction of the Democratic party] justify hostile demonstrations against us by Great Britain? 'Twould be truly dosing him with his own medicine, should war befall us from these unpaid State debts during Mr. Polk's Administration.
From "Mr. John C. Rives," in the [Washington, D.C.] Daily Union (April 2, 1851):
A page of the Congressional Globe and Appendix contains 6,693 brevier ems, and the Congress page contains 2,870 brevier ems. It follows that Mr. Rives's allowance of 75 cents a page brevier for the congressional pages, is a fraction less than $1[.]75 a page for the Congressional Globe and Appendix. He puts presswork at 25 cents a ream when estimating the presswork done at the Union office, and he allows 10 per cent. on the cost of paper to cover all other expenses. Now, we have all the items necessary for our purpose ; which is to give Mr. Rives a dose of his own medicine: [table of calculations omitted].
From Charles Coffin, Four Years of Fighting: A Volume of Personal Observation with the Army and Navy (1866), describing the Union army's advance toward Memphis after the Battle of Shiloh in April 1862:
The brutality of the [mule] drivers is terrible. A miserable fellow, destitute of sense and humanity, strikes a mule over the head, felling the animal to the ground. Noble horses are remorselessly cut up by these fiendish beings in human form. There is no check on their cruelty. You see dead horses everywhere. All the finer sensibilities become callous. One must see, but not feel. There would be pleasure in snatching a whip from the hands of these savages and giving them a dose of their own medicine.
From remarks of Senator Chambers in The Congressional Globe (April or May 1869) urging adoption of a Proclamation of Neutrality with regard to Great Britain and Abyssinia mimicking the British Proclamation of Neutrality of 1862 [combined snippets]:
Whenever a ship-of-war of ours [during the U.S. Civil War] chased a rebel steamer into a British port anywhere on earth they [the British, in accordance with its Proclamation of Neutrality] brought the American ship-of-war to, under the guns of their forts, and they would not permit her to leave that port until the rebel cruiser had had twenty-four hours within which to get away. I would serve the Abyssinians in the same way. If they attempted to get up steam or even to lift their anchor I would sink the Abyssinian ship-of-war that was chasing a British ship; and I would do the same on the other side. I would observe perfect neutrality. I am in favor of giving Great Britain a dose of her own medicine, and not a homeopathic one, either.
'A taste of [one's] own medicine'
The first example of this expression is from the Richmond [Virginia] Dispatch, reprinted in the Yazoo [Mississippi] Democrat (December 24, 1859):
THE BANNER TO STAND OR DIE BY—Under this head, the infamous book of Helper, indorsed by the Governor of New York and sixty-eight members of Congress, merchants, manufacturers, &c., has this among its recommendations:
"No patronage to pro-slavery merchants; no guestship in slave-waiting hotels; no fees to pro-slavery lawyers; no employment of pro-slavery physicians; no audience to pro-slavery parsons."
People of the South, will you not retaliate upon these men in their own kind? Will you not give them a taste of their own medicine?—Richmond Dispatch.
From "Stinging Speech of Mr. Van Wyck of New York -- The Chivalry Enraged by His Home-Thrusts" in the Cleveland [Ohio] Morning Leader (March 17, 1860):
The speech was finished amid the ferocious scowls of the disunion Democrats. A taste of their own medicine threw them into a paroxysm of rage. Perhaps it will teach them to be more circumspect hereafter in their assaults upon the people of the North.
From the [Wheeling, Virginia] Daily Intelligencer (August 29, 1860):
A Breckenridge orator at Vicksburg [Mississippi] suggested that the Douglas men should not be allowed to speak there. The Aberdeen Conservative replies with great spirit, asserting the right of free speech, and declaring that the Douglas men will not only speak, but that they will freely expose the schemes for the disruption of the Union. The Douglas men have been quite willing to aid in suppressing the freedom of speech in its application to Republicans. They naturally dislike the taste of their own medicine. By and by it may occur to them that the most effectual way to secure their own rights is to respect the rights of others.
From the Montgomery [Alabama] Ledger, quoted in Whitelaw Reid, After the War: A Southern Tour: May 1, 1865, to May 1, 1866 (1866):
States reduced to Territories? Indeed a little move in that direction would be of service, we think, in bringing about a full restoration of harmony between the section. A little taste of their own medicine.
From "The Trial of Ghosts," in The Youth's Companion (October 3, 1872):
"Bue it might frighten her,—might frighten her to death, you know."
"Nonsense, she's tough! And besides, if she makes other people think she sees ghosts, it's no more than fair to let her have a taste of her own medicine."
“It seems mean, any way," said Tom, uneasily.
And from a letter on the subject of alcohol prohibition, dated July 19, 1874, in The Index (August 6, 1874):
Suppose, now, that the Legislature of Massachusetts, impressed with these convictions, should pass a law suppressing the Sunday utterances of Dr. Miner, and his Universalist brethren throughout the State, and, in case of uproarious persistence on their part to inculcate their dangerous "views," should lock up their meeting-houses, and send the preachers to jail ; that would be giving the Doctor a taste of his own medicine which might, or might not, work well.
The saying seems to have originated as "a dose of [one's] own medicine" (in use by 1834) and later expanded to include the variant wording "a taste of [one's] own medicine" (in use by 1859). I didn't find any evidence from nineteenth-century sources that a particular incident or story might have served as the source of the expression. It seems more likely to me that in the 1800s most people regarded the bitterness (and dubiousness) of medicinal remedies as a commonplace, and found it natural to equate a doctor's being forced to take his own medicine with a person's having had done unto him or her some unpleasant thing that he or she had previously done unto others.