Personally I'd go with PCI-Express if I were building a new machine at this moment in time...AGP is gonna phase out over the next 12 months (perhaps a little longer). Unless you already have the mobo and it's an AGP one, I'd get a PCI version instead - better future proofing (whatever that means!).
Also, I reckon nVidia still have the edge in the vid market - get a good solid 6800GT and overclock it. Even with a stock cooler it will easily clock faster than it's big brother the 'Ultra' - add a custom cooler and you could do even better.
Note: Half Life 2 was supposedly made 'native' to ATI cards, and ATI spent £6m sponsoring the game and bundling it with their cards. It really ****es them off that HL2 creator Valve's own survey of thousands of HL2 players shows that nVidia is the game players popular choice.
Having said all that the ATI card is a top end piece of kit