Вы запрашиваете «больше ИЛИ меньше на 1», поэтому поместите это ИЛИ в свой код вместо AND:
coordinates = [(6, 3), (4, 2), (5, 3), (2, 4)]
found = []
for c in coordinates:
if ((c[0]+1, c[1]) in coordinates) or ((c[0]-1, c[1]) in coordinates):
found.append(c)
found
теперь содержит [(6, 3), (5, 3)]