I'm highly dubious about McCain being the nominee in 2004, and roughly equally dubious about the nigh-on universal assumption on here that Gore loses in 2004. When incumbent presidents lose, it's generally because they've hit the buffers in a big, palpable way, usually obviously so in terms of the economy and party management (Carter 1980, Bush 1992), neither of which I really see transpiring in 2004. It's lazy to write Gore off in 2004.
Equally I don't really think it's an easy path for McCain swinging from being the candidate of Rolling Stone and winning open primaries on the back of Democrat and independent votes to being the presumptive Republican nominee all in a few years. I guess there's the national security factor, but that didn't guarantee him the nomination in 2008, when, like Kerry four years before, his candidacy nearly collapsed in the invisible primary. (And he'd had the time to go out of his way to suck up to Republican interest groups)