For text-based conversations I can use Adium to talk to anyone on a PC, regardless of their IM client. For voice chat, both Mac and PC can use Skype. For video chat, however, it's much harder.
The general convention had been to use iChat with an iSight (or a USB webcam using unofficial drivers) on the Mac and AIM with a USB webcam (mostly Logitech QuickCams) on the PC. The latest version of Aim (Triton) broke that by not being video-interoperable with iChat. At about the same time, Skype gained video support (in beta), but only in the PC version. Google is also funding development of video in libgaim, used by Adium and Gaim.
Ideally, either Skype will have video support on all platforms (more likely) or Adium will get video support that can talk to all the major networks via libgaim (less likely), but for now—until AIM or iChat gets patched—I'm going to give yak a try. I haven't actually tested it yet, and it seems to be a bit unofficial so far, but the messaging is SIP-based (i.e. an open protocol, unlike Skype) and supposed to work on both Mac and PC.
The other thing is that the iSight uses a Firewire connection, but there was a rumour that the new Intel iBooks won't have Firewire connections at all, so maybe there will be a new USB-based iSight (apparently the iSights built into new G5s use USB connections) released soon as well.