He would have tried to build on former Whigs, both Unionists and reluctant secessionists who had resisted it but "gone with their states" after its passage.
He'd want all Blacks to have the same civil rights as whites, ie the right to marry legally, own property, sue and be sued etc. He seems to have been treading warily about giving them the vote, suggesting in his last public speech that it be given to Coloured Union veterans and to "the very intelligent" however that be defined. However, if the Southerners were as mulish as OTL with their "Black Codes" etc I could imagine him going further. How much further is anybody's guess. If he goes for universal suffrage it will provoke the same backlash as OTL, most likely with the same result.
If he goes for something like the 14th Amendment[1] , but not the Fifteenth, Southern representation in the HoR and Electoral College is sharply reduced. So the GOP may win the1876 election w/o dispute. Cleveland may lose in 1884, but if the Republicans hold power too long they will wear out their welcome sooner or later and there'll be a backlash against them. No one hangs on to power forever.
He might also have looked for a way to enable those Blacks who had been given land in the Sea Islands and elsewhere to keep it, even if they had to start paying rent to the heirs, as and when the Rebel owners died off.
He would try to form a viable Unionist in the South, but I doubt if he would succeed. One big problem is that the GOP were the party of high tariffs, which of course meant higher prices for imported goods, something which obviously hits the poor most. Poor Blacks would likely overlook this out of gratitude for emancipation, but poor *Whites* obviously wouldn't. Also, the former Whigs to whom he would look as the core of his Union Party would in many cases be planters, ie better off Whites rather than poor ones.
All in all, by the 1880s things probably aren't that much different from OTL, though hopefully there'll have been less bloodshed getting there.
Threads like this are where I'll really miss David T. He was great on US history ones.
[1] Probably without Section 3, which he would resist as a blatant encroachment on his pardoning power. Also, w/o Andrew Johnson the Republicans may not see it as necessary.