I'd go with an Nvidia Geforce FX 5900 or Radeon 9800 Pro; actually back in 2003 I combined a Radeon 9800 Pro with an AMD Athlon 2600 XP.
A working Radeon 9800 Pro can be hard to find though as they are prone to memory failure.

Herewith an article with HL2 benchmarks https://www.anandtech.com/show/1546/2

UT2004 will depend how demanding you are.
I thought the game was playable with a P3-866 and a Geforce3, but that was a long time ago.
It was definitely decent on an Epox AMD760 motherboard (EP-8K7A+? something like that) with a midrange Athlon and a Ti4200.
My standards weren't very high though. I'm not much of an FPS player and I don't compete online, I just play single player against bots.

I have an old spreadsheet from benchmarking the AMD760 machine and it says the CPU was a 1600/133, doesn't specify the core type, Ti4200 128MB card. I was getting between 30-60fps depending on map type/etc. I had the graphic details mostly set to "Normal".
Slowest map I tested was AS-Convoy. With memory clocked at DDR266 CL2, it ran 29.8fps at 1280x1024x32, 32.6fps at 800x600x32.
DM-Rankin was ~60fps at 800x600, didn't try higher res.
If you want maxed details or 60fps then it won't be fast enough for that, but it's decent.

Rankin is small and has only one bot by default. Not exactly good representation of UT2004 content.

That's why I also mentioned AS-Convoy.

I played doom iii on a 3200+ and a radeon 9800 pro. it was doable, but less then optimal. I would go a few generations a head of a 9800 pro. an x1950 perhaps?