I'd suggest the Voodoo 3 2000. Its a pretty good card on slow systems and the price is below $100. The speed is great especially running on glide games. So far one of my computers that run with the V3 2k is capable of running almost every game that i play.
In the "stay away from" department, I'd like to nominate the Viper II. Bough one recently just to see if it's as bad as I hear. And it is. (Ok, so it's got to be the dumbest possible reason to buy a video card, but see my signature )
Don't get me wrong, the card itself seems to be very fast (for a SDR board, and for that price.) Especially in multi-textured games, like Unreal Tournament, it runs like the wind. But the drivers are not just bad, they're a total catastrophe.
If the new S3-VIA joint can make good drivers and maybe a DDR based version, we could have a major ***-kicking card. But here and now... just avoid it.
On the other hand, in the "very good bang per buck" department, my favourite would be a Matrox G400. (Normal, not Max, since a 350 MHz isn't enough to actually saturate the cheaper card's fill rate anyway.) It's got excellent image quality, the drivers are excellent quality, too, and it's more than fast enough for a 350 MHz Pentium. In fact, until you get around an Athlon 600 MHz level, it will be the CPU, not the G400 that limits you. (And after that level, you can safely overclock it by 10% or so, with the MgaTweak program.)
Been using a G400 for half a year now, and I'm happy as a clam with it. My only sorrow is that I didn't get the more expensive G400Max instead, since on my 750 MHz Athlon the normal one hits the fill rate limit. (Though, don't get me wrong, I still get extremely good fps in 1024x768 on most Unreal Tournament levels. That fill rate isn't GeForce class, but it's damn good anyway.)
Moraelin -- the proud member of the Idiots' Guild
OK, when your friend said: "he doesn't think it came with any kind of video card (?)", that means it's some all-in-one mobo. So, you can't get an AGP card, it'll have to be a PCI card. But, you should "open the hood" and take a look first.
If it is an all-in-one mobo, I second JM's advice: get a Voodoo3 2000 PCI card for $85 or so. It's a good performer for a reasonable price. Here's a good vendor that has a retail PCI version for $85.