You can get a Matrox G450 card, well supported under X in any distribution you care to name, or get a wild and wooly ATI RADEON card and go for the bleeding-edge drivers. By the time you get this, expect to see the RADEON support cleaned up quite a bit, but it still could be a project to install and not a “click OK” like the Matrox.
Why not NVIDIA? VA Linux Systems did proprietary drivers for the NVIDIA GeForce2 in early 2000, which confused a lot of us considering the whole “open-source” story VA was selling to customers and investors. But the last thing you want anywhere near the low levels of your system is software that you, or more likely, your distribution's X experts, aren't allowed to fix. Think, people! Proprietary OSes flake out more often than Linux does. Buy into one vendor's broken-software-by-law license model, and they'll all be trying it next year. Then where will you be? Besides, master Linux 3-D hacker Daryll Strauss says RADEON performance is about the same as the GeForce2.
I'm running the prerelease Debian packages of X version 4.1.0-2, as provided by Debian's X Strike Force; other distributions have prerelease X packages out too. The RADEON also requires kernel support, which is another reason to get the latest 2.4 kernel on the system right away.