any tricks to get foreign key constraint builds faster

I am in the process of implementing cascade on delete constraints
retroactively on rather large tables so I can cleanly remove deprecated
data. The problem is recreating some foreign key constraints on tables of
55 million rows+ was taking much longer than the maintenance window I had,
and now I am looking for tricks to speed up the process, hopefully there is
something obvious i am overlooking.

BEGIN;
ALTER TABLE ONLY t1 DROP CONSTRAINT fk_t1_t2_id;
ALTER TABLE ONLY t1 ADD CONSTRAINT fk_t1_t2_id FOREIGN KEY(id) REFERENCES
t2(id)
ON DELETE CASCADE
DEFERRABLE INITIALLY DEFERRED;
COMMIT;

t1 has 55 million rows
t2 has 72 million rows

I have tried set constraints deferred, immediate, the id column on table 2
is indexed, its the primary key. There may be memory settings to tweak, I
was able to get it to run on a faster test server with local storage in
about 10 minutes, but it was running for over an hour in our production
environment.. We took down the application and I verified it wasnt waiting
for an exclusive lock on the table or anything, it was running the alter
table command for that duration.

An additional question - is there any way to check how long postgres is
estimating an operation will take to complete while it is running?