That is, for someone to be able to communicate with me securely and anonymously over the secure Tox network, can one person use Toxic and the other person use μTox?
Yes, they are capable of speaking the same protocol, and communicating with each other.
Every client listed on https://wiki.tox.im/Client has the ability to speak with each other at the basic level. In the table at the bottom, you will find a list of clients and the features they support. When two clients that share a capability talk with each other, they can also use that capability between them.