You didn't specify what you will be using the machine for. Dos games? Early windows games with 3D acceleration? If you only plan to play DOS games on it in software mode (no 3d acceleration) get an S3 Trio64 / S3 Virge or a Cirrus Logic 54xx. If you want 3D acceleration, most games of the era use GLIDE. That means you need a 3DFX card. The simplest options for your machine would be a PCI Voodoo Banshee or Voodoo 3. These support glide so you can run early 3d accelerated games like GL_Quake, Tomb Raider, Carmageddon, Descent, Quake 2 and alike. There's also stuff like Pandemonium that will only run on a 3dfx card, so if you're building a machine that can run ALL games up to say 1998 you need a 3dfx card.
I'd match a Banshee with a pentium pro. Sure, the Voodoo 2 might be faster (slightly) in some games, but the Banshee is a single card solution (unlike the V2) and it will do higher resolutions and it has more video memory. The Voodoo 3 is even faster (a little faster then two Voodoo 2 cards in SLi) but finding a PCI version won't be easy / cheap.
The trick to Voodoo cards is that they are less dependant on your CPU then modern video cards like the Radeon 7000 you wanted to purchase initially. The R7000 needs CPU overhead the Pentium Pro can't provide, while say a voodoo 2 would actually offload some tasks from the CPU, improving performance. Using a Voodoo card it's possible to get playable framerates from GL_Quake @ 640x480 ON A FAST 486 machine with hardware acceleration - 22 to 27 fps, versus 16-18 fps in software mode in dos, 320x240 - so keep that in mind. Sure, the voodoo kind of expensive, but you get what you pay for. In the long run, it might cost more to go the cheaper route (the radeon 7000 / matrox G450) when you find games that won't run - or won't run well and wind up going for period-correct stuff or abandoning the build altogether. If you're going to go cheap, get an S3 Trio64 or a Virge and be done with it - those can be had for 5-10$.
In such a machine, the best combination that will allow you to play games up to 1997-1998, including really old stuff, an S3 / Cirrus Logic PCI 2D card + 3DFX Voodoo 2 3D accelerator would serve you best. Matrox card aren't known for their compatibility with DOS games - some will display graphical glitches (especially on newer cards like the G450!). Games like Jazz Jackrabbit, Commander Keen, Golden Axe, God of Thunder, Supaplex and others get choppy scrolling, stuttering or just flat-out refuse to work on some matrox cards. They are best suited for high-resolution windows GUI acceleration. Also consider the G450 is pretty new and un-suited for the pentium pro - it's a card that would have been found in pentium III systems, two generations away.
You can use this chart for DOS games video card compatibility: http://gona.mactar.hu/DOS_TESTS/ - S3, Cirrus Logic, Trident (PCI) and nVidia cards are best suited for DOS games. Early ATi Mach64 PCI cards (witch is missing from the chart) are also great for DOS games.