The cat poop thing is a bit of a non discussion for me: generally, they're pretty neat and will bury theirs. Dogs don't, and some owners don't bother clearing up after them, or leave their wee bags as unwanted decorations in trees or bushes.
The birds thing is fair enough. One of my cats, Tango, used to have a particularly disgusting habit of catching and chomping seagulls, but leaving the wings as a delightful gift of her prowess by the back door. Not a discovery you want to step into barefooted on a dark morning when you're taking the bins out.
As for the dogs, I voted for the land shark option, just because it made me smile. I don't really think there's an easy solution, as I was taught pretty early on that dogs, no matter how docile or friendly they may seem, can lose the plot for any number of reasons.