Para cibercafé: Procesador Memoria o AGP

Con las maquinas de hoy en día un navegador no ha de tener problemas en funcionar desahogadamente. Si que es cierto que cuanta más máquina mejor, y cuata más memoria... pero con los mínimos que tu me has dicho (un AMD 1.2 con 128 de RAM), es más que suficiente. Quizás con más RAM podrías abrir de forma ligera muchas más páginas de vez, pero no hay mucha gente que navegue con más de 15 abiertas a la vez ;P
EL procesador cuando llegamos a estos niveles (un 1.2 y un 1.8) no se nota mucho la diferencia. Piensa que cuando navegas por internet lo que haces es recibir y enviar datos y luego en tu máquina procesarlos. Por tanto en la navegación lo que más ha de contar es el ancho de banda (como muy bien has dicho), teniendo en cuenta las máquinas que me has mencionado. (Un 486 con 8 MB de RAM lo notarías por mucho que tuvieras un gran ancho de banda).
Y por la tarjeta de video tampoco es muy importante... evidentemente cuanto mejor sea mayor rendimiento podrás sacar, pero para navegar la verdad que no te has de complicar mucho la vida. Eso si, si hay juegos en el cybercafé si que tendrías que replantarte esta cuestión principalmente y intentar de tener las mejores máquinas que tu bolsillo soporten, ya que los juegos son los que mejor hardware necessitan y más recursos consumen.
El cuanto a software lo ideal seria usar un sistema GNU (Linux, BSD...) ya que son gratuitos, mucho más estables, permiten una mayor administración y están completamente orientados a trabajar en red.
Aunque si prefieres Windows yo te recomendaría por los mismos motivos que te he dicho de los GNU (menos el precio), Windows XP/2000/NT, en este orden. Aún así Windows 98 te puede también ir bien, pero que sea el SE.
Si necesitas más información o bien no he resuelto tus dudas.

De acuerdo a lo que me dices, te recomiendo un equipo mayor a un Pentium II de 450 Mhz con 128 Mbytes de Ram, en cuanto a la cantidad de RAM del Video o velocidad de acceso del disco, no tiene mayor relevancia en Banda ancha, pues la velocidad de la Banda ancha es mucho menor a la velocidad de estos dispositivos, así que con un equipo mayor al que te menciono, da lo mismo para tratar de navegar más rapido, lo otro es que no cargues programas en forma continua como Kazaa, Imesh, etc. que si te ocupan recursos de tu Banda Ancha, Saludos espero que te halla servido mi consejo...

La velocidad de navegación principalmente depende del ancho de banda de la línea que tengas con tu ISP y de la propia calidad del ISP, o lo que es lo mismo del ancho de banda que tenga el ISP que te da servicio.
La potencia del equipo, sirve principalmente para procesar la información gráfica de las ventanas, poder tener varias abiertas al mismo tiempo y poder también tener otras aplicaciones abiertas.
Con relación a tus preguntas:
1. La respuesta sería afirmativa teniendo en cuenta que en ambos casos tienes el mismo ancho de banda.
2.Para navegar no se nota la diferencia de 256 a 512 a día de hoy. Esto quiere decir que conforme pasa el tiempo, los diseños web cada vez están más elaborados y requerirán mejores capacidades de máquina.
Si el precio no es un problema te recomiendo poner 512.
3. La buena aceleradora de video descarga el procesado de la CPU de la máquina y por tanto mejora el rendimiento. En este caso la respuesta sería similar a la anterior.
Respecto al sw no puedo darte ninguna información sobre W98se.