【2021/10/15 追記】
この記事は更新が停止されています。現在ではブラウザの動作が変化している可能性もありますので，過去の記事として参考程度にご覧ください。

追記

今回参考にさせていただいた記事はこちら。
http://d.hatena.ne.jp/maachang/20110730/1312008966

この内容をもとにPHPで関数化してみました。

function download($input_filename, $output_filename = '') {
    static $pattern = '/Chrome|Firefox|(Opera)|(MSIE|IEMobile)|(Safari)/';
    if (headers_sent() || ($size = @filesize($input_filename)) === false) {
        return false;
    }
    if ((string)$output_filename === '') {
        $output_filename = $input_filename;
    }
    $output_filename = mb_convert_encoding(
        $output_filename,
        'UTF-8',
        'ASCII,JIS,UTF-8,CP51932,SJIS-win'
    );
    switch (true) {
        case !isset($_SERVER['HTTP_USER_AGENT']):
        case !preg_match($pattern, $_SERVER['HTTP_USER_AGENT'], $matches):
        case !isset($matches[1]):
            $enc = '=?utf-8?B?' . base64_encode($output_filename) . '?=';
            header('Content-Disposition: attachment; filename="' . $enc . '"');
            break;
        case !isset($matches[2]):
            $enc = "utf-8'ja'" . urlencode($output_filename);
            header('Content-Disposition: attachment; filename*=' . $enc);
            break;
        case !isset($matches[3]):
            $enc = urlencode($output_filename);
            header('Content-Disposition: attachment; filename="' . $enc . '"');
            break;
        default:
            header('Content-Disposition: attachment; filename="' .$output_filename . '"');
    }
    $finfo = new finfo(FILEINFO_MIME);
    header('Content-Type: ' . $finfo->file($input_filename));
    header('Content-Length: ' . $size);
    return readfile($input_filename);
}

$input_filename はロケールにあったエンコーディングで渡してください。
$output_filename を省略した場合は $input_filename がそのまま使われます。
$output_filename は自動的にUTF-8に変換されます。
成功するとダウンロードさせたファイルのサイズ、失敗するとFALSEを返します。

Windowsでの使用例

download(mb_convert_encoding('あいうえお.jpg', 'SJIS-win', 'UTF-8'));

IE9以降・Chrome14以降・その他ブラウザの挙動は未確認なので検証していただけましたらご報告いただけると幸いです。