Aquí os dejo el código final y funciona correctamente:
<?
$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==".") { echo " "; } else if ($archivo=="..") { echo " "; } else {
// 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>";
}
?>