I think that simulating coroutines by explicitly building the call stack they would have had isn't too ugly. This solution only conses to build those call stacks:

    (defun leaves (tree)
      "Return a function that returns the leaves of TREE one by one when called repeatedly."
      (let ((work (list tree)))
        (flet ((schedule (x) (when x (push x work))))
          (lambda ()
            (loop for task = (pop work)
                  until (atom task)
                  do (schedule (cdr task))
                     (schedule (car task))
                  finally (return task))))))

    (defun same-fringe-p (t1 t2)
      (loop with l1 = (leaves t1) and l2 = (leaves t2)
            for x1 = (funcall l1) and x2 = (funcall l2)
            while (or x1 x2) always (eql x1 x2)))