Melhor maneira de excluir milhões de linhas por ID

Tudo depende ...

Supondo que sem acesso de gravação simultâneo para as tabelas envolvidas ou você pode ter que bloquear as tabelas exclusivamente ou esta rota pode não ser para você.
Exclua todos os índices (possivelmente exceto os necessários para a própria exclusão).
Recrie-os depois. Isso é normalmente muito mais rápido do que atualizações incrementais de índices.
Verifique se você possui gatilhos que podem ser excluídos/desativados com segurança temporariamente.
As chaves estrangeiras fazem referência à sua tabela? Eles podem ser excluídos? Excluído temporariamente?
Dependendo de suas configurações de autovacuum, pode ajuda a executar VACUUM ANALYZE antes da operação.
Alguns dos pontos listados no capítulo relacionado do manual Preenchendo um Banco de Dados também pode ser útil, dependendo da sua configuração.
Se você excluir grandes porções da tabela e o restante caber na RAM, a maneira mais rápida e fácil pode ser esta:

BEGIN; -- typically faster and safer wrapped in a single transaction

SET LOCAL temp_buffers = '1000MB'; -- enough to hold the temp table

CREATE TEMP TABLE tmp AS
SELECT t.*
FROM   tbl t
LEFT   JOIN del_list d USING (id)
WHERE  d.id IS NULL;      -- copy surviving rows into temporary table

TRUNCATE tbl;             -- empty table - truncate is very fast for big tables

INSERT INTO tbl
SELECT * FROM tmp;        -- insert back surviving rows.
-- ORDER BY ?             -- optionally order favorably while being at it

COMMIT;

Dessa forma, você não precisa recriar visualizações, chaves estrangeiras ou outros objetos dependentes. E você obtém uma mesa imaculada (classificada) sem inchaço.

Leia sobre os temp_buffers configuração no manual. Este método é rápido desde que a tabela caiba na memória, ou pelo menos na maior parte dela. O wrapper de transação protege contra a perda de dados se o servidor travar no meio desta operação.

Execute VACUUM ANALYZE mais tarde. Ou VACUUM FULL ANALYZE se você quiser trazê-lo para o tamanho mínimo (pega cadeado exclusivo). Para tabelas grandes, considere as alternativas CLUSTER / pg_repack ou similar:

Otimizar o intervalo de consulta de carimbo de data/hora do Postgres

Para tabelas pequenas, um simples DELETE em vez de TRUNCATE muitas vezes é mais rápido:

DELETE FROM tbl t
USING  del_list d
WHERE  t.id = d.id;

Ler as Observações seção para TRUNCATE no manual. Em particular (como também apontou Pedro em seu comentário):

TRUNCATE não pode ser usado em uma tabela que tenha referências de chave estrangeira de outras tabelas, a menos que todas essas tabelas também sejam truncadas no mesmo comando. [...]

TRUNCATE não irá disparar nenhum ON DELETE gatilhos que podem existir para as tabelas.