Well, you already identified the one I would typically suggest - the concurrent skiplist, but the absence of other specific requirements other than the three above, I think a simple linked list with per-node mutexes will work:
Each node contains one element (or a reference), and one simple mutex. I'll assume Java here, because it helps avoid race conditions around node reclamation.
Searching through the list consists of iterating through the nodes from the head, no need to get any locks (although you'll need to ensure visibility between threads at some point - you can choose how frequently this happens - once per search may be good enough).
To add an item, do a search until you find the immediate predecessor and successor nodes for the value you want to insert, lock the mutex associated with the prior node, check the successor node again (it might have changed out from under you), then splice in the new node.
Deletion works similarly - find the predecessor node for the node you want to delete, lock the predecessor node, check that it is still the predecessor node, and take it out of the tree.
This structure is sorted (to the extent that it is correct - I haven't proven that!).
This structure clearly allows multiple readers (readers are never blocked for any reason), and multiple writers, although writers trying to manipulate the same portion of the list (e.g., two threads inserting nodes which have the same splice point) will wait on each other.
The structure seems relatively easy to reason about - being based on a single linked list, with a fairly simple locking structure and with a few simple invariants. I haven't spend more than a few minutes reasoning about its correctness, however. You can make it even simpler to reason about, at the cost of performance, by making the locking policy more heavyweight - for insertion and deletion lock each node during iteration and then lock the successor before unlocking the prior node - in this way you'll have both nodes locked when you find the splice or deletion point, so no "double-check, backtrack" is needed.
You may be able to get rid of the locks completely and use a lock-free list while maintaining your "must be sorted" condition, but I haven't thought about it in depth - at a minimum I suspect it will be "harder to reason about".
In C++ the structure is more involved, since you can't rely on the GC to keep the nodes around as long as readers might be looking at them, so the simple strategy of allowing the readers to mosey around in a lock-free manner doesn't fly, if you ever want to delete nodes. You can adjust it by making readers take the lock of each visited node, but this sucks for both performance (obvious) and concurrency (because although you can have multiple readers and writers in some basic way, they can never pass each other anymore, so practical concurrency is heavily limited).
An alternative would be to use rwlocks in each node, readers taking read locks only and inserters/deleters taking read locks to find the position to work on, then upgrading to write. Currency is at least improved since readers can pass readers, but writers still block readers (so all readers that are iterating at a position before some node on which a write operation starts will not be able to iterate past that node until the operation completes).
Now, all that said (whew!) I should mention that other that "easy to reason about" this structure seems pretty much inferior to the concurrent skip list in every material way, with the possible exception of slightly less memory usage (maybe). It doesn't have the log(N) search behavior, in particular. It is not fully lock-free (writers may wait on writers in some cases). I'm not even sure it is that much easier to reason about as far as concurrency goes, although the underlying structure is simple.
I think if you really wanted you could extend this kind of "per-node" locking to something like an rb-tree if you wanted, but it not easy. In particular, you need to find some kind of node to lock prior to any tree rotations that is "high enough" that you can be sure that any thread wanting to perform a modification that will affect the correctness of your rotation will also try to lock the same node. In the linked list, this is the "predecessor node" - in an AVL or RB-tree it is not so simple.