¿Cómo crear un índice único con condicional y subconsulta en PostgreSQL?

La desventaja de usar reglas es que las reglas simplemente reescriben la consulta después de analizarla, por lo que si los datos se agregan a través de un activador, no se activará. Es más seguro agregar una restricción CHECK que llame a una función con su lógica. Si sigo tu lógica correctamente, debería ser algo como:

CREATE OR REPLACE FUNCTION check_user_client(fkc int) 
  RETURNS boolean AS
$$
DECLARE
  i int;
BEGIN
  SELECT count(*) INTO i FROM legal_entity WHERE fk_client = fkc;
  IF (i > 0) THEN
    RETURN true;
  END IF;

  SELECT count(*) INTO i FROM user_client WHERE fk_client = fkc;
  IF (i = 0) THEN
    RETURN true;
  END IF;

  RETURN false;  
END
$$ LANGUAGE plpgsql;

ALTER TABLE user_client ADD CONSTRAINT unique_user CHECK (check_user_client(fk_client));