Tienes que leer el directorio (sus archivos) .. almacenarlos en un array -> ordenar el array y luego presentar leer ese nuevo array (ordenado) para representar tus links o resto de código:
   Código PHP:
    <?
$archivos=array();
$dir="fotos/";
$directorio=opendir($dir); 
echo "<b>Directorio actual:</b> <br>   $dir<br>"; 
echo "<b>Archivos:</b> <br>"; 
while ($archivo = readdir($directorio)) {
// Incluyo chequeo para no almacenar las entradas de directorios ni directorios (is_dir())
   if ($archivo !="." && $archivo !=".." && !is_dir($archivo)) { 
       // acomulas los nombres de archivos en un array.
      $archivos[]=$archivo;
  } 
}
closedir; 
 
// Ordenas tu array:
sort($archivos); 
// (y mueves el puntero interno del array al principio ..)
reset($archivos); 
 
// Lees tu array de $archivos
foreach ($archivos as $archivo){
   echo "<p>";
   $archivo2=$archivo;
   $archivo = str_replace("_", " ", $archivo);
   echo "<a href=\"fotos.php?seccion=$archivo2\" target=\"_blank\">$archivo</a>";   
}
?>    
  
Un saludo,