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.

As you can see it deleted both cats. Well, in the meantime I solved my problem with Drop.

That's fine for a single element, of course DeleteCases can also handle it:

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

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

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}