Could Plessey vs Fergusen have gone the other way?
If Grover Cleveland wasn't elected, that's rather simple.
Not really -- it was 8-1 OTL, with five of the pro-segregation votes coming from other Presidents (and even prior to Cleveland's first election in 1884, you have at least two of them). It's not enough to take out one President -- if you're going to solve this with the guy making the appointments (a risky venture, since Supreme Court appointments of the 19th Century had a complex sort of politics), you'd have to at least start with seeing a pro-Civil Rights President in office at the time.
How about this then -- Cleveland still wins in 1884, and gets to appoint Muller to Chief Justice (so that's three anti-votes, to Harlan's); however, in 1888, Republicans decide to nominate somebody other than Harrison (which was
very possible), who is also an old friend to the ideals of Reconstruction (maybe John Sherman?). This President wins and is re-elected, meaning come 1896, he's appointed five justices to the court.
Even with all this, you still have the
Civil Rights Cases to deal with as precedent, and the fact is Harlan's position in
Plessy may well be, by this point in legal history, to be considered an extreme position.