Something of a maverick, especially in the south, Estes Kefauver might be a reasonable choice for the Dems in '56. He'd be palatable to northerners. If he chose John F. Kennedy as his running mate, 1956 probably wouldn't be a landslide as it was IOTL--close, but not quite: after all, we're talking Ike as an incumbent.
Stevenson in '60--if he manages to pull it off--probably means another Midwesterner (Humphrey would be my guess) as his running mate. That removes Lodge as Nixon's running mate, meaning someone like one of the Mortons (Rogers or Thruston) or maybe MD governor McKeldin. Any of them would bring more to the table than did Lodge.
The '60 campaign would have the potential of getting nasty, though. Stevenson had a quick wit, and wouldn't have hesitated to use it on Nixon. On the flip side, Nixon would probably say that Stevenson is wasting time joking rather than focusing on issues. Then it escalates, with the barbs getting sharper. Also, I don't see debates happening. On the whole, the GOP would likely unite behind Nixon focusing on the memory of Stevenson in '52 (and the mud McCarthy threw at him). The '60 election would be razor thin as IOTL, but I think Ike's successor would be Nixon rather than Stevenson.
Interesting butterflies: no Kennedy in '60 (maybe '64?), and no Lyndon Johnson (probably remains in the Senate; don't know if he'd be able to work with Nixon as he did with Ike). Probably no Goldwater, either. Viet Nam might be replaced by Cuba as the third rail of American foreign policy.