Any external hard drive will work with PCs or Macs, as long as the connectors are there (Firewire, USB, etc.) It doesn't matter how the drive is formatted out of the box, since you can re-format any way you like. Formatting in HFS (Mac OS Extended) or FAT32 or NTFS-3G can be done with the Mac OS X Disk Utility.
FAT32
Read/Write FAT32 from both native Windows and native Mac OS X.
If you're migrating to OSX then NTFS seems like you're best bet to start off with, which is what I did for example to migrate my iTunes library from Windows to my new MBP. GGJstudios's post makes me think NTFS-3G will be best for you.
Yes, USB is the same speed, regardless of the computer. The same is true for firewire. The reason you see firewire recommendations is that it is much faster than USB.... especially Firewire 800... more than twice as fast. That makes file transfers much faster, but USB will still work.