We've had posts about a President Muskie before. But how about making his presidency surprisingly early?
POD: JFK is stopped on the first ballot at the Democratic national convention in 1960. Ultimately, Symington or LBJ or Stevenson is nominated--in any event, a Protestant. The nominee wants a Catholic running mate to offer some consolation to Catholics who angrily think (with some reason) that JFK lost the presidential nomination due to his religion. The surprise choice is Muskie. He has experience as both governor and senator; he has shown he can win in an historically Republican state; and while he is from a small state, his being Polish-American can help the Democrats in large states with a significant Polish-American vote, like Illinois and Michigan and Pennsylvania, etc.
The Democratic national ticket narrowly wins. Then, three years later in Dallas...