A new video card would be fine, granted that you could find it in PCI form with an ADC or DVI port on the back. The beige G3's still used Apple monitor connections, which was pre-VGA even, so you'd need an Apple-VGA adaptor, then a VGA-DVI or VGA-ADC adaptor, degrading the signal quality greatly. I recommend looking for a good 3rd-party VGA monitor, even if it's not as good as Apple's monitors.
Apple's monitors use ADC, which means only new computers or graphics cards with ADC ports can use them. You can get DVI-ADC adaptors easily, so if you find a PCI graphics card with a DVI port you'll be set.