There are fifty thousand threads on this on MacRumors....
Option 1: iChat (Mac), AIM (PC). If this isn't working for you, it's because of firewall setups....
Option 2: aMSN or Mercury Messenger (Google them) on Mac, MSN on PC.
Option 3: Yahoo on both clients.
Option 4: Find a web-based client that uses Flash or Java.
Ditto the firewall setup issue if options 2 and 3 don't work for you. If this is the case, the first thing to do is move both the PC and the Mac into the DMZs of their routers and either open their firewalls temporarily or open the ports that the client uses.
FWIW, I'm pretty sure that the MSN option should work at least so-so without opening ports.