2000 Election:
First we have to figure out how he gets into power. There are two routes: A) a minor change on election day (or in the campaign) that results in the count more clearly favoring Gore. This is actually a fairly substantial change since it removes the legacies of OTL's gridlock and the travesty of Bush v. Gore. At its maximum extent, I think this would be Gore winning in Tennessee and maybe one other state, with Florida not decisively changing anything. Or, B), a change during the process of the counting / recounting results in Gore winning Florida by virtue of a judicial process of some sort. For example, this might be SCOTUS refusing to hear Bush v. Gore and/or allowing a recount to proceed. The issue here is whether Gore's presidency starts under the onus of a legal challenge or not.
9/11:
Consensus seems to be that it would probably happen (and for argument sake positing that it wouldn't happen would so drastically change the nature of the 2000s that it's outside the bounds of the OP). I agree with those who say that Gore would invade Afghanistan, with NATO help.
2000 Budget surplus:
Would Gore really be able to stick to his guns and use the surplus to paydown Social Security et al in the face of a Republican Congress? At the very least, he will probably be able to stall until 9/11. After this point, the politics are a lot different. On the one hand, the GOP will want a tax cut, justified by the need to jumpstart the economy after the combination of the tech bust and the impact of 9/11. On the other, the Dems have control of the Senate (assuming Liberman is replaced by a Dem) with Liberman's veto (and with Jeffords' potential defection). Gore can potentially play hard ball at this point: the war in Afghanistan will costs lots of money, new money will need to be spent on national defense and security concerns -- he gets to justify arguing against a tax cut scheme by saying he's strong on defense. This is pretty major hardball, though, so a middle-class tax cut may also get through as a compromise. Definitely not the scale of the Bush tax cuts.
2002 Mid-Term elections:
OTL the 2002 mid-terms were a big fluke in that the incumbent party gained seats; this has been chalked up to 9/11. While TTL the GOP might attack the Dems for allowing the attack to happen in the first place -- an attack the GOP can make more easily than the Dems TTL since they can blame Clinton too -- they don't get to run on the strongest theme they did OTL: support the commander in chief / gov't in a time of crisis. Indeed, a lot depends here on how Gore handles the response to 9/11 and how people feel about it. Will Lieberman end up in an "undisclosed location"? Will Gore fumble in the same way Bush did on 9/11 itself (his press conference at the AFB)? Will Gore have the same sort of moment with the fire fighters at Ground Zero that Bush did? What will Gore's Joint-Address to Congress be like? Will he be strong, insisting on the moral uprightness of the USA or will he admit a role for US (and hence some blame) in allowing extremism to fester? I'd like to think his response would probably have been strong, but without the bluster (Axis of Evil) of GWB. On the other hand, though, the GOP will still try to say he wasn't hard enough. Another factor at play is the legacy of how Gore won in 2000, whether by judicial action or not. At the end of the day, though, I think a Gore White House will be able to get an approval bump from the whole thing, given the nature of the American people's response to the attack (return to patriotism). Hence, the Dems probably do "well" in 2002. Of course, that doesn't mean they take back the House or anything. Maybe just narrow the margin in the House and gain a Senate seat. Would have to look at what seats are open in 2002 and likely candidates for TTL.
The outcome of the above is probably that the GOP vs. Dem stand-off increases by virtue of an even more divided gov't than OTL. Gore will have gotten any victories by playing on the impact of 9/11 (as any post-9/11 president would have). To knock him off his horse, the GOP would have to out-patriotism him. If in '02 the GOP hardliners do try to attack the Dems for their handling of the situation, I think it backfires to some extent due to the rally-round-the-flag effect. Therefore, by '04, they would be ready with a new strategy. In this environment, somebody like John McCain might do pretty well (though as always he'll struggle to get the support of social conservatives, who OTL were a big part of GOP strength in '02 and '04). I guess is, to whom would the social conservative torch fall and would major GOP donors line up behind them? This is a large part of the reason why GWB dominated in 2000. Personally, I think consensus is likely to be pretty well divided. For one, Jeb Bush looks like a potential candidate and if GW has had his chance, might Jeb play for his?
In summary, there are probably two options: either a social conservative emerges, who runs on social issues, or a moderate who runs on a maverick / "country - first" strategy. In the first case, 2004 may be pretty close (though Gore's incumbency would help him and the GOP wouldn't have the power of the White House to put behind a get-out-the-vote campaign). In the second, though, the election may not be partisan, though it may still be fairly close. The middle ground would probably be someone who could do a bit of both. George Allen may work as would Tom Ridge. Come to think of it, Giuliani (assuming he comes out of 9/11 smelling like a rose) might try for the nomination, too. I doubt he takes it, but he would introduce an element of profound unceratinty into the GOP convention / primaries. Personally, I don't think Elizabeth Dole would have enough, current expereince in 2004 (even assuming she's in the Senate after '02). She's a good VP pick, though.
2008 is a bigger question, in my mind. The Credit Bubble will still be growing, but if tax policy since 2001 has been different, it may take slightly different paths. Plus the truly shocking parts of the financial crisis didn't really happen until September - October 2008. Before then, a changed invasion of Iraq (or probable lack thereof) dramatically changes the feel of 2004-2008. Hillary is almost surely running for the nomination in '08 and Obama probably hasn't risen to prominence as fast (at least not in the way he did OTL). In short, it's possible the butterflies change the "major events" (Bear Stearns collapse, Lehman Bro.s bankruptcy, AIG bailout, non-passage of TARP, passage of TARP, bungling of TARP, etc) of the crisis in such a way that the election of 2008 TTL is very, very different from OTL. That being said, given the fact that a downturn had been brewing since 2007 probably means that there's at least enough of a recession in the air (per Clinton in 1992) that the incumbent will be disadvantaged. Odds are, President Hillary Rodham Clinton is sworn in January 20, 2009.