One encounter you could do early on would be to have the party enter an alley and suddenly come upon a rat feasting on a dead bird or something... Anyone in the campaign world would know (possibly with an easy Int check) that the average rat would flee instantly if discovered out in the open.
However, instead of skittering away in panic, the rat bares its teeth and advances on the party hissing viciously.
Depending on how hard you want to push the scene, it may well follow the party out of the alley into the middle of a busy street and/or begin attacking if the party doesn't retreat quickly enough. If engaged, the rat fights to the death without hesitation.
It should be enough of a wtf moment that the party finds it highly disturbing.
Using it right near the beginning of the adventure would be a great way of either introducing the problem or escalating it. At the very least, even if the possibility of plague is off the table, the party still has to wonder if they're dealing with an impending rabies outbreak.