"Tables seem to be the big pain point. Possibly conses too[...]"
I could be wrong, but I think it's enough for a table to extend 'keys, function call behavior, and 'sref. <Insert usual disclaimer that there'd need to be predicates like 'supports-keys in the absence of failcall.>
For Penknife's purposes, the only reason I care about cons cells is that they're eager implementations of nonempty lazy lists. They should support function call behavior, 'sref, and the one and only lazy list operation:
(iffirst first rest seq
<...thing to do with first and rest if the seq isn't empty...>
<...thing to do if the seq is empty...>)
If cons cells are mutable and allowed to be improper, then they need 'scdr too, and it might be more elegant to add 'scar, 'car, and 'cdr.