Most monitors with DVI also have analog inputs. It's not the conversion from analog to digital that hurts performance, performance is ok with or without, but visual quality is degraded by using analog at all, instead of a digital link starting at the video card and staying digital.
Using a very high quality and shortest possible analog cable will help, some, but at 20" and larger panels' native resolutions you are reaching the limit of what analog can transmit without blurring.
Whether your card is PCI or AGP makes no difference in output quality, bus speeds higher than 32bit/33MHz PCI is only needed for gaming or related high texture bandwidth uses you wont' have with 2D windows or movie playback. However, if you buy a new card you should get AGP because it relieves the PCI bus of traffic making other PCI devices have more bandwidth remaining. It effects some people more than others depending on what else is on the bus - things like certain sound cards, PCI IDE or SATA controller cards, heavily utilized USB2 or Firewire, TV tuner/capture or Gigabit ethernet cards are among those that benefit most from minimizing # of other PCI cards in use.
HDMI link is for HD movie support and is the only link you'd need (for 2D windows/etc use too), but your present system is a bit slow for HD playback due to the CPU unless you bought a current generation video card with full HD decoding support. IMO the ability to watch HD movies is not as important as that of improving system performance for all the more common tasks done on a PC, unless you don't have a larger TV you'd want to use instead to watch movies.
If it's really going to be a while till you upgrade the system you might think about adding a 512MB memory module as there are a lot of tasks that exceed 512MB, and even when they don't, having more memory for a presistent filecache that isn't flushed out often gives better performance than having to reread everything from HDD several times, BUT some PIII chipsets dont' support over 512 to 768MB of memory like i815/440ZX in the former and 440BX in the latter case. It would seem you don't have 440ZX or BX since they only have AGP 2X support not 4X.
While it is slow by gamers standards, the following $20 Radeon 7000 looks like a good match for your legacy AGP slot, using minimal power and quiet since it has no fan (plus the DVI out of course, I dont' think you will find an old AGP 2X/4X card with HDMI, maybe not even a PCI card with HDMI).
http://www.newegg.com/Product/Product.aspx?Item=N82E16814241057
If you're really concerned about HDMI and HD video viewing, it's time to buy a new system or more substantially upgrade the present motherboard, CPU, memory, video, PSU. In the US this is not very expensive. Bargain hunter website forums have had skt. AM2 boards for under $50 after a rebate, AM2 X2 CPu for about $50 and up, and a gig or two of memory for almost free. Likewise with PSU there have been Coolermaster and other 500-600W for $10 after a rebate, you could have a substantial upgrade for about $115-140 if that's all you could budget for it, and sooner or later your old parts will die of old age, making it cheaper to buy when you see deals rather than an emergency situation later.