I think Condoleeza Rice would be a good choice, to give the ticket some foreign policy credentials. I think Meg Whitman would have been a top choice for him had she won the Governorship (they are close friends, successful businesswoman, from a large state). Kay Bailey Hutchison would be a possibility too, for reasons previously stated.
Like John McCain before him, I don't think Mitt Romney is in any position to be picking anyone perceived to be a moderate by the GOP base. If he is going to nominate a member of the fairer sex, she is going to have to be a Tea Party darling like Sarah Palin or Michele Bachmann.