How to avoid deadlocks in Postgres?

Ordering statements at the application level is a good solution in that it avoids database overhead. The statements would need to keep their order per-table. If this is easily workable in the application, it's worthwhile.

There is also a solution at the database level: serializable isolation.

The Serializable isolation level provides the strictest transaction isolation. This level emulates serial transaction execution for all committed transactions; as if transactions had been executed one after another, serially, rather than concurrently. However, like the Repeatable Read level, applications using this level must be prepared to retry transactions due to serialization failures. In fact, this isolation level works exactly the same as Repeatable Read except that it monitors for conditions which could make execution of a concurrent set of serializable transactions behave in a manner inconsistent with all possible serial (one at a time) executions of those transactions.

You can set this isolation level when you start your transactions. This does add some database overhead, but more importantly the application must be ready to catch serialization failures and retry the transaction.