have Lincoln choose a Radical VP, and you might get Atzerodt assigned to Seward and Powell attacking the VP, with Atzerodt looking, at least in hindsight, like the least dependable. This in itself creates interesting butterflies.
Presuming the VP survives (maybe it *is* Seward in fact) he could run again in 1868. Have him put Grant in the Cabinet for a little longer and learn how to do politics without involving all his corrupt friends, as noted; perhaps this president introduces him to people who he can feel comfotable with.
Maybe have a Democrat win in 1880 then, due to public tiredness with the REpublicans, and then havce Garfield serve 8 years with the Republicans back in power.