Where could McCain get a "WOW"? The most obvious choice would be Secretary of State Condoleezza Rice. Her intellect and genuine model of feminism (moving up without a husband to blaze the path) make her very attractive. She's identified with the Iraq War, but no more so than McCain himself, and her forthright battle against Iranian and North Korean nuclear ambitions would burnish her credentials.
But Condi may not want it. Her predecessor as secretary of state, General Colin Powell would also bring a pretty good sized "WOW" with him. While he was tarnished by the false intelligence information on which he relied to defend the Iraq War in the United Nations, Powell still has plenty of star dust. And both Powell and Rice know how to handle themselves under pressure.
Or McCain could cross party lines and choose Connecticut Democratic Senator Joseph Lieberman. By demonstrating that his candidacy is truly post-partisan, McCain could be the first presidential candidate to run on a coalition ticket since Abraham Lincoln did it at the height of the Civil War in 1864. The prospect of a bi-partisan ticket would be irresistible to many swing voters and would graphically offer rebuttal to the charge that McCain is just Bush III.
Even if Rice says no, McCain could still achieve a "WOW" by choosing a woman for his ticket. But here he has to be careful. There is no clear standout choice among GOP female senators or governors. To reach down and tap one of those who are available could carry a risk that she would not be able to handle herself well at the national level.
So Obama needs a VP who offers reassurance and McCain needs a WOW. No ordinary running mate will do for either ticket.