I don't think Jim Crow laws have to be have been as extreme as they were for as long as they were, being up to the 1950s/60s. However, it's true that Southern society as a whole needed to be changed.
I do, though, think that - by eliminating the biggest problems - Jim Crow can be toned down and wind up not lasting as long. (Unless, of course, you're talking more years of military presence than I think anyone was willing to put up with.)
How soon can it come? If President Lincoln manages to survive, especially in a shorter Civil War by 18 months like "If Baseball Integrated Early," then there isn't the intense Northern anger. Yes, he'd probably still have to focus on ending some of the violence, even if he tries to get poor whites and ex-slaves to come together politically. the amount, I leave to those more expert int he area. However, if you have the vigilantes/terrrists stopped by Federal troops right away, so such actions are clearly Federal crimes, then you have at least somewhat less of a problem.
Use Federal law enforcement only to stop that, and not to totally dominate the entire South, and I think you see two things: 1. It can last for a longer time, so there's not as much impatience; 2. Less Southern hostility toward the North in general. They'll say, "Hey, they haven't tried to overwhelm us, they're just enforcing laws against one specific type of problem." Laws that they might be able to get a fair number of Southerns to support.
With that, yes, Lincoln's legacy is that of a milder Reconstruction that just never quite worked to give the ex-slaves all the equality they needed. However, it might prevent the worst of the Jim Crow laws. the South of 1900 might be like the North of 1900 in OTL as far as the way discrimination goes. I think that, as society focuses on the extreme abuses against blacks, suddenly, you can see things start to get a little better. Immediate enforcement, coupled with a lack of Northern occupation of the South, could prevent the Klan from coming back as a political force in the 1910s, as the author of the book that inspired "Birth of a Nation" in OTL sees them in a very negative light. (he writes a different book, inspring a different movie, in my book, focusing on General Lee.)
Then what? A generation grows up in the 1870s and 1880s which doesn't recall the extreme bitterness of a harsh Reconstruction, and only hears of the Federal government doing enough to prevent widespread mayhem, that's all. They learn to be more lenient, see lynching as bad, and - in a society where blacks are a little freer - a Civil Rights movement can start in the 1910s or 1920s. And, when Federal legislation is proposed, it's not hated quite as much. Southern states might even pass some themselves.
Of course, you need a lot of things to go right, which is why I throw in baseball being integrated from the beginning, which is my focus anyway

Seeing great black stars on a national stage, under limits like the NFL had in the 1950s and 1960s (2 blacks per team) till the early 1900s when one manager pushes for more, allows just one more way for people to see that they can be together in public, on the same team. (Octavius Catto also survives, which helps a lot, too.)
A Civil Rights movement before the 1910s or 1920s, thugh, would be very hard. Unless, as I noted, there's such extreme Federal domination in the 1860s, 1870s, maybe 1880s, that it totally tears Southern society apart.