For an otherwise superb API, my only real criticism of Java Collections is that there is not a fine enough level of granularity that separates the CRUD (Create, Read, Update, Delete) actions on a Collection. It is either modifiable or non-modifiable, but even this is only achieved as a thin wrapper (specifically, it uses the Decorator pattern) over an already existing Collection and as such both a modifiable Collection and unmodifiable Collection will be a reference type of Collection. This makes it essential to document (or in the worst case assume) whether or not a Collection can be changed, and the true intent can only be discovered at runtime when an Exception could be thrown.
In some cases, it is approriate to return a reference type of Iterable to express your intent that the items are only meant for iterating over, but this is not always the case, as sometimes you might want to return a read-only List (since List offers random access and operations such as size()). In a rarer case, you might want to have a Collection where you can add elements but not remove them (as one example).
I am not suggesting to neccesarily have different implementations of Collection classes to achieve this, but to at least provide more strongly-typed interfaces such as ReadonlyCollection, AddOnlyCollection, RemoveOnlyCollection, etc. For example, ArrayList could implement all three of these interfaces. Now the problem becomes someone casting to a different interface and being allowed to perform operations not from the original interface. I think this could be overcome by combining this idea with the current way (ie Decorator) that would throw a RuntimeException if someone is lame enough to cast to a different interface at runtime. I also guess this would merit a factory method for creating Lists (ie ArrayList.createReadOnly() or ArrayList.createAddOnly()) and further complicate things, but I think it's actually approriate in this case.
It makes sense to use the Decorator pattern to achieve something similar as is currently done, but again, this does not allow one to express intent at compile time. I don't think stuff like this a function of documentation, but something that can be expressed through code. Another idea is to add more Iterator types, such as SizeableIterator (that adds a size() method). Currently, if you have a Collection reference, you only know it can return an Iterator and not a ListIterator, which is also unfortunate.