For multiple elements deletion, here are some fast implementation:

Removing elements from a list which appear in another list.

If you like terse coding (not so fast really), there is a closely related topic:

In[]:=   Fold[ DeleteCases[ ##, 1, 1]&, {cat, dog, fish, dog, cat, dog, cat, fish}, {cat, fish, cat}]
Out[]:=  {dog, dog, dog, cat, fish}

What the documentation says is accurate, as the returned elements are indeed in canonical order.

  In[1]:= Complement[{c, b, a, c}, {c}]

  Out[1]= {a, b}

  In[2]:= % === Sort[%]

  Out[2]= True

The functions Union, Complement and Intersection are designed to work as the usual set-theoretic union, complement and intersection if the list arguments are considered as sets (which means repeated elements are ignored). This is explicitly documented for Union and Intersection. For example,

In[3]:= Intersection[{b, a, a, a}, {b, a, a}]

Out[3]= {a, b}

and again the result is sorted.

Thanks guys, The major reason I wrote in the first place was the misstatement in the documentation that Complement does a sort. If it would have done a Sort, everything would be just fine, because Sort does not eliminate duplicates. Yes, I always want to drop the first one because of the time dependence. Drop, Delete and DeleteCases are taking more time than Complement. In the case of big lists that is significant.

If your list contains sets of identical items, and you want just one of them dropped, which one is it that you want dropped? So this is much like you did above. If it is the first occurrence, we can just find its position in the list and drop it:

In[1]:= list = {dog, dog, cat, fish , cat, dog}

Out[1]= {dog, dog, cat, fish, cat, dog}

In[2]:= dropFrom[list_, thing_] := 
 Drop[list, Position[list, thing, 1, 1] // Flatten]

In[3]:= dropFrom[list, cat]

Out[3]= {dog, dog, fish, cat, dog}

In[4]:= dropFrom[list, bear]

Out[4]= {dog, dog, cat, fish, cat, dog}

In[1]:= DeleteCases[{cat, dog, fish, dog, cat}, fish]

Out[1]= {cat, dog, dog, cat}

In[2]:= DeleteCases[{cat, dog, fish, dog, cat}, Alternatives @@ {cat, fish}]

Out[2]= {dog, dog}