I find removing packages a hard problem. Typically I work around it by starting with a minimal base image that doesn't have anything offending.
-> nothing related to avahi shows up for me, ping and dnslookup all work fine for me.
But to remove packages on an existing system I like to use dselect and with it I can find my way around. However I know the tool is mostly replaced by more modern tools like aptitude, and dselect is known to be tricky to use right. But for me it works - even though working through dependecy issues can be quite challenging, and quite often I give up and abort all changes - as some package turns out to be too essential to make removing it or replacing it easy.
If that is an option for you I'd spend my time starting small and carefully adding packages to find what broke your system (and reinstall once more without that extra component if necessary). But that only works for me as my little computers are just toys without essential data and I have a stack of five to play with.
Andreas