How about Obama/Biden vs. Bush/Cheney with no term limits?
Given Bush's deep unpopularity, this map might have been possible:
Senator Barack Obama(D-IL)/Senator Joe Biden (D-DE): 472 Electoral Votes
President George W. Bush (R-TX)/Vice-President Dick Cheney (R-WY): 66 Electoral Votes
President Bush's best state would have been Oklahoma, where he would have gotten around 56% of the vote, while Obama would have definitely received 60%-70% of the vote in many states. In addition, a larger win for Obama might have been enough for the Democrats to defeat Saxby Chambliss, Roger Wicker, Lindsey Graham, Mitch McConnell and maybe Susan Collins in their respective Senate races, thus giving the Democrats their largest Senate majority since the 1960s.
If you figure that George W. Bush would have been reduced to holding seven [7] states, then revise your map and trade the hues of Mississippi and Texas.