Well, if we look at the second half of 19th century politics, we can start to see which groups might coalesce into our opposition party. As stated, labor and and immigrants are almost certainly a given; even liberal members of the GOP were hardly favorable to either group (with the important cavaet that if said immigrants were Protestants, especially Germans or Scandinavians, they were okay). We then can add to this, farmers; though this group is more of a swing constituency, esecially in the Midwest and East. Although we often point to the Populists as the great upswelling of agrarian unrest, it actually started in the 1870s with the organization of the Grange Movement and the rise of the Greenback Party. Now, lets throw dissatisfied Republicans into the mix; the Liberal Republicans were the most obvious example in OTL, but there were ther dissenters from the Republican Party as time moved one. Some of these were moved by a genuine desire to end Reconstruction early because they wished to end the sectional divide in the country, feared the growing power of the federal government and denounced corruption (I'll leave it up to the reader to decide how much they believed this, and how much was antipathy towards Civil Rights), but there were others who opposed the dominant strain of Republican thought at the time which was growing cozier to big business and corruption. Due to the harsher war, the anti-Civil Rights side of thing will be muted, here.
Okay, so that's the North (in a nutshell. One could go into a lot more detail, of course). Now for the South. We know that the planter class is going to be politically decapitated here; as the strongest supporters of the rebellion, they are going to be crushed and there is likely to be some major land redistribution. So lets leave them out for right now. So, who else is left for our opposition party? Well, for the first generation or so, the Freedmen vote is going to be almost exclusively GOP I suspect for a number of fairly obvious reasons. However, white Southron small farmers would be natural allies over time (they will likely lean GOP due to the land distribution at first, but as economic issues grow, I think they will defect enmass), along with laborers in the mining regions as well as the steel production areas.
I think there's every reason to assume that the Bourbon Democrats of OTL could eventually move their way into the GOP of this ATL, as it grows more keen on classical liberalism (well, somewhat. It's hard to fully embrace that notion after your party oversaw land redistribution and the enforcement of Civil Rights; though I suspect many will come to see that as a neccesary war measure and not exactly a precedent for future actions. At least until the Progressive Era). And as such, the New Elite in the South - because there WILL be a new elite; nature abhores a vacuum after all - could potentially follow suite. Hell, a sizable part of the new elite might well start off as Republicans, either because they are some of those farmers who benefited from land redistribution and struck it lucky, or because they are carpetbaggers.
So, basically, we are left with a new opposition party that is most definitely a Farm-Labor Party. It's not Socialist (there are too many constiuencies here that would take an ill look to that), but there are probably many conservative social democrats within it's ranks. In an ATL where Cleveland doesn't go out strike bashing, there's not even any reason to assume that Debbs defects to, first, the Populists and then the Social Democratic Party; and do the world of Until Every Drop of Blood is Paid is one where we could see a Debbs-Bryan ticket in 1892
(and yes, THAT would be amazing. Debbs is a sadly under utilized figure on this board).