Kettle of fish
This term is usually part of 'a fine kettle of fish', 'a pretty kettle of fish' etc, which mean 'a muddle or awkward state of affairs'. The expression 'a different kettle of fish' has, as seems fitting, a different meaning, which is 'an alternative; a different thing altogether'.
Being English, I have a close association with kettles - essential equipment for a custom that the English can still claim world dominance, the making of 'a nice cup of tea'. Tea-kettles were first named in the early 18th century; until then 'kettle' referred to any vessel for boiling water. The noun 'kettle of fish' is listed by several reference works as dating from 1745, although the earliest actual citation of the term in print that I can find is in Thomas Newte's A tour in England and Scotland in 1785:
"It is customary for the gentlemen who live near the Tweed to entertain their neighbours and friends with a Fete Champetre, which they call giving 'a kettle of fish'. Tents or marquees are pitched near the flowery banks of the river... a fire is kindled, and live salmon thrown into boiling kettles."
The French term fête-champêtre, meaning 'rural feast', was still in use at the time to describe outdoor meals. The word 'picnic' (also French - 'pique-nique') was introduced in the late 18th century but wasn't widely used until the end of the century.
Why a kettle of fish was chosen to represent a muddle or mess isn't clear. It may be an allusion to the confusion of bones, head and skin that is left after the fish has been eaten. It may also be that 'a pretty kettle of fish' was just pure invention, along the lines of 'a pretty pickle'. The earliest uses of the phrase, which apparently are examples of the 'muddle' meaning come from Henry Fielding and pre-date the fête-champêtre citation above. In The history of the adventures of Joseph Andrews, 1742, he writes:
"'Here's a pretty kettle of fish', cries Mrs. Tow-wouse."
and, in The history of Tom Jones, 1749:
"Fine doings at my house! A rare kettle of fish I have discovered at last."
If those examples from Fielding aren't entirely clear in their meaning we do get an unambiguous explanation of the phrase in Francis Grose’s Dictionary of the Vulgar Tongue, 1811:
"When a person has perplexed his affairs in general, or any particular business, he is said to have made a fine kettle of fish of it."
'A different kettle of fish' is much later and is known since the 1920s. By that time 'kettle of fish' had been appropriated to mean simply 'state of affairs'.