What do the different colours of Quest mean? I'm guessing that it has to do with the value of the quest?

(Also, the wording "Municipal pound looking for a female cockatrice" is really ominous sounding to me... it isn't possible for quests to do anything to your pets, right, because it is really worrying me)

It's fine, your pets are returned to you exactly as you left them. It's just a little flavor text. You will always get your pet back, barring any major bugs.