A lógica é simplíssima: você mantém os arquivos com os nomes originais no sistema e quando for enviar para download mande-o com outro nome
public static void Download(string fName)
{
FileInfo fInfo = new FileInfo(fName);
HttpContext.Current.Response.Clear();
HttpContext.Current.Response.ContentType = "application/octet-stream";
HttpContext.Current.Response.AddHeader("Content-Disposition", "attachment; filename=\"" + Guid.NewGuid() + "\""".pdf\""); // Aqui está o segredo
HttpContext.Current.Response.AddHeader("Content-Length", fInfo.Length.ToString());
HttpContext.Current.Response.Flush();
HttpContext.Current.Response.WriteFile(fInfo.FullName);
fInfo = null;
}