I had an elven cat in a 2nd edition campaign I was running in FR. An elven cat looks just like a normal cat but is actually a fey creature and quite intellegent (INT 16). They have a number of cool innate abilities like
invisibility, enlarge (self only), jump, pass without trace, and trip. This particular Elven Cat also happened to be an 11th level pschoportive psionist able to fly, travel ethereally, and teleport. She was a proxy for Rillafane the elven god of the forest and decided to help the PCs for awhile because she had a crush on the party bard.
You could aways go with annoying but otherwise normal cat, but if the PCs harm it in anyway, it offends some god favourably disposed towards cats. Soon the party is being followed by a small pack of angry feral cats that steal food and damage items in camp at night, draw predators and beasts into their camp, draw attention to the PCs whenever they are trying to be quiet, and show an unhealthy amount of interest in anything the PCs do.
If the PCs harm or kill any of these cats, then more and more start to show up and become agressive, doing hit and run attacks on the guilty PC, when vulnerable, before scattering. Maybe even bigger more dangerous cats, celestial cats or lycanthropes begin besetting the party if they make it their agenda to kill all the cats around them.