If Colin Powell didn't go for the Republican nomination in 1996 (when, in all likelihood he would have won the general ) I doubt he'd take the 2000 nomination. He really is too moderate for Republican primaries, after all.
2000 is an interesting question, though, with no George Bush and Jeb Bush (only two years into his term) probably not going for it. I'm tempted to say it's McCain's year, but he can't handle a frontrunning campaign (as 2007 proved) so he really does need somebody to play off of.
If butterflies keep Newt Gingrich is good standing, he probably has a good chance.
If Alan Keyes somehow managed to win the 2000 Republican primaries (i.e. via an alien mind control ray he picked up) he'd be trounced by Gore.
One of the also-rans of OTL 2000 might catch fire, there was a big list (Elizabeth Dole, Lamar Alexander, Steve Forbes, Dan Quayle, and even more lower profile people).
As for the general I expect it's Gore favoured against anybody but McCain, and even McCain would have enough troubles with the base (remember, this is before he flipped to agree with the base on all the big issues—and even after that, i.e. now, he's still having trouble with them) that his swing voters are keeping him in the running instead of heading for a landslide.
That said, Gore Vs. McCain is probably McCain favoured.