Clinton would pick another moderate/conservative Democrat, likely someone in the Democratic Leadership Council (DLC), because he wouldn't want to risk the GOP hitting him with being too liberal. Most likely, the VP will be someone from the South or Midwest, regions of the country not typically associated with "liberalism" like the East Coast or California is. He would also need to be someone who would be acceptable to the left of the party, so it couldn't be someone like Pennsylvania Governor Bob Casey who was against abortion.
The most likely candidate might be Bob Kerrey as RogueBeaver suggested. I defnitely know he was on the short list of VP picks. Other possible contenders might be Sam Nunn or John Breaux - all southerners associated with the DLC. I think Nunn would be a particularly strong candidate. Gephardt, another DLC member, is likely seen as too pro-union to have the crossover appeal Clinton was looking for.