Biggest difference: if McCain passes tax cuts at all, they're much smaller. He uses the remaining surpluses (until the dot com bust eliminates much of them) to pay off large amounts of debt.
As to the 9/11 speculation, from the 9/11 Comissions Report it does appear that parts of the Federal government may have information relating to the attacks, but I agree with those who suggest that a change of the Presidency in January isn't necessarily going to shake up the bureacracy in time to stop the hijackers. One of the big issue of the 2000 election foreign policy wise was GWB effort to curtail foreign adventurism. McCain probably has different thoughts on this, but I doubt he campaigns on the need to confront terrorism.
There might still be butterfly effects: for example, I seem to remember that there an ambassador's wife (or maybe a low level undersecretary) was on the plane that hit the Pentagon. Change around the people appointed becuase of a different election and you get different people on the flights then maybe you might change the circumstances behind whatever happened on Flight 93 (probably not) or maybe you might have it on the other flights.
I also expect that McCain will make a bit greater use of NATO's invocation of mutual attack. Perhaps some reform and mission change (i.e. transforming NATO into a worldwide Alliance for Democracy) might occur.
Also, Jim Jeffords of Vermont might not trigger the temporary Democratic control of the Senate. He might be less likely to switch if McCain is the leader of the GOP.
I am trying to think of just how McCain might have won in 2000:
1) Ann Richards manages to defeat GW Bush in 1994 so he isn't in the running. Lots of butterflies before 2000, though.
2) Some kind of major Bush gaffe in South Carolina and/or release of the stories about his lack of attendence during his Ntl. Guard Service earlier.
3) Karl Rove has a heart attack before the campaign begins.
4) Another conservative candidate runs as well, spliting the far right's votes. Potential people: Newt Gingrich, unlikely given his resingation in 1998. Rick Santorum? Best bet is probably John Ashcroft
Also, I've been wondering if McCain's nomination (likely a close fight) might alter Gore's strategy. Particularly, I'm wondering if Gore might pick a different VP and if it might be Paul Wellstone (to prevent Nader from outflanking the campaign). Certainly we might get butterflies that prevent his untimely death in 2002. While I don't think Gore could manage a win against McCain (even if Gore wins Florida, which I doubt with McCain, I think McCain might win PA and certainly NM); a Gore-Wellstone ticket might, because it potentially changes places like the Dakotas or Missouri. Things might be harder still, if McCain is forced to pick someone very conservative for his VP.