As I understand it, Grand was really loved by Lincoln for his tenacity even before Vicksburg, and certainly after. I think Grant would be given command of the AotP without the interim - though whether he is placed there right away, I'm not sure. Meade's reluctance to attack entrenched positions the rest of the way in 1863 also played a part, I think, and so Grant and Sherman might just slug it out with the Confederates in Mississippi, perhaps taking Meridian a lot earlier.
I think where you'd see a bigger difference is in the Georgia region, where Rosecrans would suddenly have a *lot* more credibility. While I don't see him being moved to the AotP, I can see LIncoln asking him to try to move on Atlanta and their massive rail network, which would be interesting.
You might also see a better attempt as taking Mobile, Alabama. I'm not sure how readily they would move Sherman's men anywhere close, but that was seen as one of the major objectives.
On the Confederate side, if Bragg can't hold Chickamauga, I don't care how close he is to Jefferson Davis, he's getting the axe, though he'd probably be offered the chance to resign instead. He would have given up Chattanooga on his own to drop back there and then lost in what he claimed to be the best place to counter the Union. I suppose Longstreet could take the blame instead, but Lee did still rely on him so he'd probably just gets sent back there.
As to who replaces Bragg? Johnston versus Rosecrans would be interesting, but perhaps in this situation, Hardee would be willing. He wouldn't have been in the situation where he'd feel like Davis took Bragg's side like when the junior officers all asked for his removal earlier. In this spot, Davis would probably reluctantly ask Bragg to leave. So, perhaps Hardee and Rosecrans - which would be interesting.Hardee seems like he'd be better, perhaps, than Bragg or Johnston. (Then again, some of you all might be bettter than Bragg.

)