Thanks to both comments, maybe I was not clear enough and want to clarify: I was not suggesting to remove conformance to either Collection or Sequence but, maybe, to deprecate and offer an alternative to some of its methods when used on a Dictionary.
In fact, since no solution has been proposed yet, I would prefer to focus more on understanding use cases and/or direct usage of those methods (first, firstIndex etc...) instead 
Edit: I modified the title of the original post to better reflect this goal.