how deep should categories be in order to be user friendly?
Make them shallow enough to allow for a rich (and useful) set of (search) filters to also exist.
On pets, as you mentioned, "Dogs", "Cats", "Rodents" and so on would be valid categories. "Breed", "colour", "intelligence" and so on should be considered filters, and should be combinable (e.g. to find dogs of a particular breed and also of a particular colour).
Filters should also be presented separately from the category trees, in a form that fits them, such as multiple-selection listboxes.
In short: build a category tree. See at what level it starts to make sense to combine different paths, to get more complete results. Also search for repetitions (see my diagram below, where the two breeds would have identical "subcategories"). Everything from there on should be considered filters.
Filters usually start two levels or so in.
(Teal colored are categories; yellow colored are filters)