El punto 1 depende de como hagas lo de "descargar". Si simplemente es con el "Guardar imagen", creo que siempre guarda con el nombre especificado en el src del img. Podrias configurar el servidor para poder poner en ese src el nombre de de la imagen, usando las mismas tecnicas que para crear URLs amigables para buscadores:
http://zonaphp.com/articulo30.php
Y sobre el espacio en disco duro, dices que el thumb ocupa 4-6kb. Eso significa que si la galeria tiene 1000 imagenes, seria simplemente unos 6 megas (que no me parece mucho). De todas formas, podrias especificar un espacio maximo en disco para los thumb (en un directorio). A la hora de mostrar los thumbs, compruebas primero si ya creaste el thumb (esta en el directorio de thumbs); si esta, muestras el fichero; si no esta, compruebas si has llegado al limite de espacio para thumbs, eliminas uno de los ficheros; y despues creas el fichero thumb. Lo ideal seria mantener en un fichero la lista de los ficheros y eliminarlos segun un criterio (el mas antiguamente accedido, el menos veces accedido, ...).
Eso si, en esta situacion ya seria evaluar si implementar esta "cache" cuesta (en recursos) mas que la generacion.
Por cierto, ahora que lo pienso, ¿cada thumb lo generas con una llamada a un script independiente? Porque si es asi, el problema esta en la ejecucion en paralelo del mismo script. Haz la prueba de aumentar en el php.ini el valor de memory_limit. Quizas mas que de velocidad, es un problema de memoria.
Suerte.