The optimization process and recommendations:

1. Create Optimal Indexes (modified query below): The recommended indexes are an integral part of this optimization effort and should be created before testing the execution duration of the optimized query.

Optimal indexes for this query:

CREATE INDEX company_idx_id_client ON "company" ("id","client");
CREATE INDEX company_idx_id_intermediary ON "company" ("id","intermediary");
CREATE INDEX company_idx_id_contractor ON "company" ("id","contractor");

The optimized query:

SELECT
        contract.id,
        (SELECT
            company.name 
        FROM
            company 
        WHERE
            company.id = company.client) AS "clientName",
        (SELECT
            company.name 
        FROM
            company 
        WHERE
            company.id = company.intermediary) AS "intermediaryName",
        (SELECT
            company.name 
        FROM
            company 
        WHERE
            company.id = company.contractor) AS "contractorName" 
    FROM
        contract