I still think that McCain had to choose a woman as his running mate, who could have picked up all those votes of the bitterly disappointed Clinton supporters, preferably a minority candidate.
With that said, his best choices would have been Condoleezza Rice or, even better, Ileana Ros-Lehtinen from the most important swing state.
I'm not sure about Ileana Ros-Lehtinen, if only because she had never won a statewide election, and I just personally would hesitate with picking Congressmen.
I actually heard that Kay Bailey Hutchison was someone they considered. I think she would have held her own as a pick, but I'm not sure how the base would have liked her and how her ties towards the oil industry in Texas would have played in a national election (remember how they went on and on and on about how Palin "stood up to big oil").
I think they considered Jindal, Pawlenty, Thune, Crist (FL), and Tom Ridge.
Ileana Ros-Lehtinen is born in Cuba...
And Palin would be useful in fight to a Democratic filibuster proof, as she would bring more votes to Stevens (who failed). Pawlenty could be useful in same way, helping Coleman. Another interesting name could be Mary Fallin, as solid conservative with three terms as Lieutenant Governor and Representative.