This link should bring you to all AGP cards that have 512 MB of ram. Be wary of the lower priced ones, though. I would recommend something in the ATi 3650 to 3850 range for decent gaming performance.
All DVI cards can do VGA out with an adaptor, which is usually supplied with the card. If not, you can pic one up for dollars.
My computer/monitor is old enough that it doesn't know what to do with DVI, even if it has a DVI- VGA adapter. SO, I need a strictly VGA slot, and all the ones at newegg are DVI.