This is a really great summary of the problems with queues in Postgres.
I ended up working around this by moving jobs to an "archived" table when they were complete, so the "hot" table never gets too large, and by avoiding long running transactions - we update jobs to in-progress, and then the worker is responsible for marking them as "complete" or "failed". If the worker crashes, a "stuck jobs" background worker will mark jobs as failed after a timeout.
Here's the one using similar approach, but for Node.js.