MPEG-1 is probably the most compatible, but like DH said, the quality is poor, and you are limited to 320x240 resolution. You can use MPEG Streamclip, ffmpegX, or QuickTime Pro (I think) to compress to MPEG-1.
Windows users can play back QuickTime if they have QuickTime installed, and MPEG-4 if they have either RealPlayer or QuickTime installed.
Mac users can play back WMV if they have Windows Media Player, Flip4Mac, or Perian installed.
Generally it is less to ask 5% of the computing population to go download Flip4Mac for free than it is to ask 90% to download QuickTime for free.