How far from the exterior?
MATLAB/Octave, 143 bytes

function [v,x,y]=d(x,y)R=S=zeros(max(y+3),max(x+3));i=sub2ind(size(S),y+2,x+2);S(i)=1;while nnz(S=imerode(S,strel('disk',1,0)))R+=S;end;v=R(i);


Ungolfed

function [v,x,y]=d(x,y)
  R=S=zeros(max(y+3),max(x+3));
  i=sub2ind(size(S),y+2,x+2);
  S(i)=1;
  while nnz(S=imerode(S,strel('disk',1,0)))
    R+=S;
  end;
  v=R(i);


Explanation

Create Source and Result matrices of appropriate size, filled with zeros.

R=S=zeros(max(y+3),max(x+3));


Calculate the linear indices that correspond to the xy-pairs, with one element padding at the borders.

i=sub2ind(size(S),y+2,x+2);


Draw the structure.

S(i)=1;


S is shown here for Example 2:

0   0   0   0   0   0   0   0   0   0   0
0   0   0   0   0   1   0   0   0   0   0
0   0   1   0   1   1   1   1   0   0   0
0   1   1   1   1   1   1   1   1   0   0
0   0   1   1   1   1   1   1   1   1   0
0   0   0   1   1   1   1   1   0   0   0
0   0   0   0   1   1   1   0   0   0   0
0   0   0   0   0   0   0   0   0   0   0


Remove all border elements by image erosion

S=imerode(S,strel('disk',1,0))


using the structuring element disk with radius 1:

0   1   0
1   1   1
0   1   0


If diagonal movement was allowed, we would instead use the rectangle:

1   1   1
1   1   1
1   1   1


Then, increment the result for all non-border elements

R+=S;


and loop until the image is completely eroded.

while nnz(S)


Return the result for each xy-pair.

v=R(i);