Virge DX? Are you kidding? (That chip is be interesting if you want to run native ports only.)
X-Files does not seem to be a 3D game.
A Permedia 2 is probably slower than a Voodoo 1 in most games, and it is supposed to need a faster CPU.

A Voodoo 1 should be ok but why not a Voodoo 2? Should be easier/cheaper to get one, and even if your CPU is the bottleneck it won't be slower than a Voodoo 1. (Of course a Voodoo 3 would be a better choice for several reasons, but since you are already struggling when updating the CPU I suppose it might not work in your system.)
Mobygames claims that both Half-Life and Starfleet Academy support Glide which would make a 3dfx card the first choice, especially since you have a slow CPU. I am not sure that this is true, though. A 3dfx card still wouldn't hurt.
There are certainly many faster cards some of which might work in your system, but I suppose you will be CPU limited anyway. (And the drivers for faster cards will probably be optimized for faster CPUs.)

HL doesn't do Glide, instead it supports 3dfx through MiniGL, much like GLQuake/Q2. A lot of games on the internet are listed as they would support Glide when they are not in fact.

I had a look at the specs of an IBM PC 350, didn't notice that you wrote the exact model before.
The S3 chip is supposed to be integrated on the mainboard. Is this the case? If it is, do you know if the PC will accept another video card at all? If not, a separate 3D accelerator like a Voodoo1/2 is probably your only option. (I won't suggest a PowerVR PCX1/2.)
The system is supposed to have a 100 watts power supply. I don't know how much a Voodoo2 uses, I only heard that they run hot.

The card is indeed integrated, which is why I'm thinking voodoo 1. I've some reservations about the board working with another PCI card, but didnt think it would hurt to try 😀

Thanks for the advice so far guys, its really appreciated.

Just go with a Voodoo. The PC 350's onboard 2D graphics chip is actually quite good so you might as well take advantage of it instead of looking for an all-in-one external solution (most of which wouldn't work with old Glide games and the like anyway)

Well at the weekend I went to a computer fair, picked up a second hand ATI Rage128 for £4 and a CD Writer for £2. I already had an optical drive, but it was from an old build and had a black fascia, which meant it looked totally out of place in the beige 90's IBM case.

Yet to test all the new goodies in the machine, but i thought i'd get the ATI just to test and establish whether or not this model will accept another video card. Might be helpful to another PC350 owner, who like me stumbled across this forum 😀

I've also managed to get myself a Voodoo 1 card with mini vga cable included. I think as others have suggested, the onboard will handle most 2D stuff pretty fine, the voodoo can take care of the D3D stuff. I really hope i can play Half Life and maybe Unreal with this new system. I've forgotten the system requirements of Unreal. Been so darn long since i played it.

The CPU is below the minimum requirements for Unreal so you won't be very happy. It will probably run, though - or should I say crawl?

The P133 matches the minimum requirements for Half-Life. It is supposed to need at least a 8MB video card but people seem to be able to play it with a Voodoo 1.

I think those two games should run fine on a modern system so I suppose you are into nostalgia?

If you're going to be playing Unreal and Half Life, I'd really suggest using a much higher end system, like something from the Pentium III era on up. Even though those games came out in the late 90's, there's nothing about them that prevents them from running well on newer systems. I can understand the nostalgia factor in playing on an older system, but frankly a lowly Pentium I just won't suffice if you want decent framerates.

Its mostly nostalgia 😁 Been using this system for a week and even though there are the obvious problems running a P133 online. It's been a lot of fun. I'm considering building something like a PII or PIII system.

Want to have a system similar to what i had back in 1998 😀

Funny you should mention P3, as I have P3 at hand. Just no slot 1 board.