We have Coyote here in SC but I NEVER see any of them. Not ever. I just stood at my back door listening to some Coyote yippen it up like crazy about 300yds in the woods behind my house but they never show themselves. Very secretive creatures. If we had the open spaces like you Westerners have then yea, I'd see them regularly but foliage hides them here. I regularly see my dogs barking at the back fence at night at what I assume is Coyote. They could easily kill my dogs if the fence weren't there.
We have few cats around here and I bet it is because the Coyote catch them.