How to improve readability of a big lisp function
Superficial

Your find-node is actually (almost) assoc or, if you prefer, (find node graph :key #'first).

Use mapcar instead of map 'list because it makes the intent clearer (the difference is that mapcar takes only lists and map any sequence).

You need just one do in loop; you can even fold all your setfs into one (setf a b c d e f).

In loop, with should (stylistically) come before for.

Deep

Your code looks too complicated for what it does.

None of your flet local functions is really necessary.
E.g., (remove-if #'is-head-p ...) should be (remove node-1 ...), 
and (remove-if #'starts-with-tail-p ...) should be (remove node-2 ... :key #'first);
this would make the code both faster and cleaner.

Your loop should be

(loop for node in (remove-duplicates (rest node-list-2))
      for match = (find-node node graph)
      for repcd = (if (eql node node-1)
                      (remove-if #'is-tail-p (rest match))
                      (map 'list #'replace-tail-for-head (rest match))))
      do (setf (rest match) (sort repcd #'&lt;))) 


General

Usually it is better to use the most specific function you need. E.g., use setq on simple variables (instead of setf which also supports general references). Use mapcar instead of map 'list when working with lists (as opposed to vectors).