Sabes trabajar con directorios? Si la respuesta es no, comienza a
leer.
Es simple lo que quieres, ve recorriendo cada carpeta por medio de opendir y un while o algo.. al tiempo que haces eso, guardas cada elemento en un arreglo, del cual luego escogeras un solo elemento mediante mt_rand(), rand() o array_rand() y listo, al tener la ruta completa del archivo que salio al azar, puedes mostrar la imagen sin problemas.
Funciones que pienso usaras: opendir, readdir, is_dir, rand/mt_rand/array_rand, closedir
Tambien se que deberas usar una funcion recursiva para leer el directorio galerias y los directorios que estan dentro de esa carpeta, y asi sucesivamente.
Sorry, es lo que se me ocurre para no hacerte yo el codigo.
Edito: Uy, me ganaron xD