В чем разница между видеокартами PCI-E и AGP, и какой из них наиболее предпочтителен для Atlon 64, 3000+ (2 GHz, 512k, 200 MHz) Socket 754 Box?

Непонятно, а какая материнская плата? Ведь карты PCI-E и AGP физически несовместимы. Поэтому надо ставить ту, под которую рассчитана материнская плата.

Разница в интерфейсе подключения видеокарты к материнской плате. PCI-E обеспечивает более быструю передачу данных, чем AGP. Если материнская плата у вас уже есть - посмотрите какой разъем установлен на ней, если еще нет, то покупка с шиной PCI-E более предпочтительна, но и более дорога.