This behavior is a great annoyance to me - I find it incredibly egregious.
How about a sign that says something like, "If you plan to hover, please lift the seat first so that it stays clean and dry for others." Evil doodlemor can think of many things to post, but they are not within the realm of polite.
The seats in the ladies room at Wegman's are always clean, because the store provides seat covers. Perhaps you could get management to supply seat covers and dispensers.
You know, the problem will end up being worse than the seats, because these squatting female canines will end up spattering the floor, too. So disgusting.