Well, there are two other limiting factors in there. One is the K6/2, since it has a very weak Floating Point Unit. Aces High depends heavily on FP operations, so it hits the weakness of that processor pretty hard. It's great that it's a 500, but I wouldn't spend big dollars on a video card, since the CPU is going to limit you to a certain degree. This is not a simple upgrade, so I think you just have to live with that one for now.
You could also use another 64 Megs of RAM. 64 is ok to run Windows, but when you start playing games, another 64 is desirable. 64 Megs of RAM is really cheap at the moment and would be an easy upgrade. A local computer store will sell it to you and install it as well. It would only take a minute.
But, you are on the right path to start with IMHO. A new video card will help a bunch, I think it is the biggest problem. With a new video card you should be able to play, although you are never going to get screaming speed out of that particular CPU. If you can swing it a V5 5500 PCI or an nVidia Geforce 2 MX PCI are the best choices. I can't find a price on a PCI version of the nVidia Geforce 2 MX, which would be the cheapest upgrade and would be plenty fast for your machine. Look around for a price on a PCI version, but the AGP versions are a great deal at under $100.
http://www.anandtech.com/showdoc.html?i=1391&p=4 Have a look at Anand's latest guide. The V5 would be sweet, but if you want the best bang for the buck you can't go wrong with the GeForce 2 MX PCI.
64 Megs of Ram should be dirt cheap. Anand has another price guide out on that one.
http://www.anandtech.com/showdoc.html?i=1395&p=2 Ya can't go wrong with $30 for a decent upgrade.

Get the Ram with beer money.

------------------
Lephturn - Chief Trainer
A member of The Flying Pigs
http://www.flyingpigs.com "A pig is a jolly companion, Boar, sow, barrow, or gilt --
A pig is a pal, who'll boost your morale, Though mountains may topple and tilt.
When they've blackballed, bamboozled, and burned you, When they've turned on you, Tory and Whig,
Though you may be thrown over by Tabby and Rover, You'll never go wrong with a pig, a pig,
You'll never go wrong with a pig!" -- Thomas Pynchon, "Gravity's Rainbow"