Although in 1996 who thought the race would be between Mayor Rudy Guiliani, that guy who just lost to Ted Kennedy, John McCain, and a new senator who was an actor vs. the first lady, an Illinois state senator, a new Senator, and an ambassador
John Edwards didn't become a senator until 1998; he was still a trial lawyer. Richardson was still in Congress in 1996.
But, if we were to extrapolate from this, here would be our frontrunners:
Gavin Newsom
John McCain
Ken Chase
Arnold Schwarzenegger (Amendment change necessary)
Laura Bush
Emil Jones
Mike Moore
Jim Webb