>>1
Dict and List are really the only ones I would expect. This is what Python does. Dict is not a sufficient substitute for List, because you want to be able to pop and insert elements into it without having to change all the indices yourself.
The underlying implementation of Dict is not really important, but I would make it optionally order-preserving (so the keys stay in insertion order, or you can sort it if you want).
As for Lists, I'd make the underlying implementation a simple Deque. If you want to do Python's tuple bullshit, don't expose it to the users of your language; make it a fully transparent optimization. You can do other optimizations if the array is huge, like changing it into a rope.
>>10
I really don't care about the underlying implementation or about re-implementing it myself; if I was worried about that sort of thing, I'd be using a lower-level language.