It seems that C# does provide both (though one is bizzarely named) so I'd just like to comment on why having both types is generally (not just in C#, about which I know little) a good idea.
There are basically two ways of implementing a map/dictionary. You can use a balanced binary tree or you can use a hash table. The first is unordered in that you can iterate over the members in key-order, and the second isn't. The ability to iterate in order is important in (for example) many text processing applications.
Tree-based maps have another advantage - they only need the types in them to supply comparison operators, where things in hash-based maps must supply a hash function. Most programmers have few problems implementing comparison, but a good hash function can be very hard to implement.
Unfortunately, tree-based maps are generally somewhat less efficient than hashed ones. My own investigations in C++ indicate that hashes are about twice as fast (which isn't such a big difference). But this is only in the general case - for example, maps where the keys are very long strings will probably be more efficiently implemented using btrees, as the comparison function does not have to consider the whole string, but the hash function does.
So there you have it, both types have their place in any good programmer's toolkit.