APPENDonly taking time proportional to the left-hand list's length?
It would be bloody hard. We'd have to avoid sequences as much as possible not only in code that has to be fast but also in code that just has to be predictable. Our programs would surely be awkward to read because of all the squirming to avoid calling sequence functions.
Thank goodness this is just a dream. It would be too silly.
Now imagine for a moment that an even more fundamental data structure lacked good and predictable behaviour that you could depend on: the pervasive garbage-collected heap. What then, I ask you?
Update: Feedback suggests that this post didn't make the point I wanted to. I hope my sbcl-devel post helps to say what I'd like to have as a Lisp user.