I always made a point of greeting any animal I met in Japan respectfully in the fashion I have described. As I went to a lot of shrines and temples I met a good few. Strangely, I was greeted with surprisingly civil responses from the animals. Not every cat bowed, or nodded their heads, but I always got at least a meow. Similarly dogs didn't always bow but at least gave me a happy bark. Crows were very respectful and always bowed. I made a point of eye contact so they knew I was speaking to them, but shifted my gaze once they could see me so as not to intimidate them, and bowed. It was great. It really added a dimension of enchantment to my time there. Of course I was not averse to slipping a healthy treat to them either if they seemed receptive. I know that this isn't necessarily a great thing to do, but still, they appreciated it I think.