I'd suggest using AVL trees with doubly chain-linked nodes. That would allow to use the same list operations for read-only access, only insertions and removals would have to use tree operations, and of course the few portions which do lookups by position would benefit from switching to tree operations, all the remaining code could stay as is. Basically, I'd use the trees as an additional data structure for fast positional lookup, not as a replacement for our linked lists. It's faster to traverse a list than to traverse a tree linearly.

(I'll reply to the remaining stuff later, I have an IRC meeting to attend now.)