Strange deadlock in foreign key check

I am seeing some odd locking behaviour when deleting a parent record
(Postgres 9.4.4).

Setup:
create table pk_rel (id int primary key);
create table fk_rel (pk_id int references pk_rel (id), x text unique);
insert into pk_rel values (1), (2);
insert into fk_rel values (1, 'a');

This example works as I expected.

Session 1:
=>begin;
=>update fk_rel set pk_id = 2;

Session 2:
=>delete from pk_rel where id = 1;
[Fails with FK violation]

But the following case, I do not understand.

Session 1:
=>begin;
=>update fk_rel set x = 'b';

Session 2:
=>delete from pk_rel where id = 1;
[Blocks waiting for Session 1]

Session 1:
=>insert into fk_rel values (1, 'a');
[Blocks waiting for Session 2]

At this point, Session 1 fails with a deadlock, and Session fails with a FK
violation.

So, why is this happening? Why doesn't Session 2 fail the FK check
immediately, like in the first case? And why is it that updating fk_rel.x
introduces a lock conflict, but updating fk_rel.pk_id does not?