In my opinion, Mark Warner is the strongest. He can position himself as a moderate without alienating the base, similar to Hillary Clinton. Gillbrand is probably the next best option, but she has to do more than be a woman to make me consider her the strongest non-Hillary Clinton candidate. It is difficult for me to say that Gillibrand would be strongest when she hasn't been forced to seriously compete for her Senate seat, since it is in New York. Warner might have coasted to the Senate, but he had to prove himself beforehand by being elected to the Governor's Mansion in swing state Virginia.
Well, she did get one of the highest re-elect percentages in NY history:
http://en.wikipedia.org/wiki/United_States_Senate_election_in_New_York,_2012