If domestic issues are the focus of the day in the 2004 election cycle, which I'd be willing to bet they would be, I think McCain might not be the best man for the nomination (assuming he even runs). Giuliani, Thompson, or maybe even Romney or Kasich would make more sense IMO. McCain's image, correctly or not, was definitely one of a man with an eye on foreign policy. But that having been said, he could still end up the nominee if the other big-name Republicans think Gore is truly unbeatable.
True. However I think Giuliani would still fail for the same reasons as in OTL 2008. It's too early for Romney, and Kasich is only a Congressman from Ohio. Thompson could be a strong candidate, but I don't think he'd beat McCain for the nomination. McCain would be the runner up from last time, and he could combine his foreign policy credentials with his experience on campaign finance reform to wage a winning campaign. One interesting aspect of all this is whether or not the McCain-Feingold Act becomes law under President Gore. That would certainly have a strong impact on the 2004 election.