Advice to upgrade graphics card

[jerry]

I currently am using a matrox marvel g400 card and it is not able to 
handle the new graphic modes now being used by ubuntu like compiz etc.
I have the intel board D865PERL and intel says it can use an AGP 2x/4x 
1.5v card. It seems that 8x will also work.
I want to upgrade the system to be able to install KDE4  and higher and 
the new graphics and eye candy that are now available in ubuntu.

Which graphics card would you recommend?
ATI or nvidia?
Some cards have 3D API directx or OpenGL or both. It would seem  best to 
get a card that has both.
Does the 3D API matter?

What is the best way to configure a new video card? Simply run:
sudo dpkg-reconfigure xserver-xorg

Do I need to install new drivers or  make changes to the kernel?
I am running 8.04.3 with KDE 3.5 and kernel 2.6.24-24 generic

After searching newegg etc it looks like a good choice for a new card 
would be the radeon HD 3850.


Any suggestions for graphics cards or configurations or howtos welcome.

Thanks for any help.
Jerry