I need a good cross-platform format for video files...

The symptom you describe sounds like an IE one, where it opens in a new window. Try the videos on Apple's site, do those play in IE on a PC while downloading? If they do then check out the html they're using to see what might be different, so that you can convince IE to keep the movie embedded in the page.

As for what would be best to do, maybe you should make both WMV and MOV.

Colin has pointed you in the correct direction.
I'll bet you're using just plain text "links" to your files. That method by-passes the browser plug-in and can cause issues (especially on Windows).
You need solid html code that gives the browser plug-in all of the needed instructions.
Another thing that may have happened is that your fast start files have lost their fast start abilities. This happens with any fast start file that is then edited and uses a regular "save". Save As will restore the fast start feature (even in files that do not normally have it).
AVI is dead. Do not use it.
Many WMP formats (codecs) are not yet ported to the Mac OS so that delivery container should also be ruled out.
H.264 Video codec (default in most Tiger app exports) also requires the viewing machine (Mac or PC) have QuickTime version 7 installed.
Since not all machines can install QT version 7 (requires 10.3.9 or Win 2000 or XP) maybe you should rule it out, too.
So.
What are we left with?
Maybe QuickTime format using MPEG-4 Video codec and AAC audio?
They would only require QuickTime version 6 be installed. Since version 6 has been around for over 5 years it may be your best option.
But you're still going to get complaints from PC viewers.

Flash (SWF over FLV) is the best option for cross-platform support.

...except that it looks horrible and doesn't play well on all machines.

The best cross-platform solution is QuickTime, and Kirk has probably the most compatible combination for more-or-less modern computers: Use MPEG-4 (or a variation thereof; I happen to like 3ivx) with AAC or MP3 audio.

If you are distributing via the Web, be sure to embed your movies properly in a web page in order to make sure that the web plugin will handle them correctly. Or use poster movies that prompt the movie to open in QuickTime Player.

--Dave Althoff, Jr.

Thanks, Dave, for the support on this issue.
But "Horror" brings up a different issue and it is worth noting the differences:
1. Most users of these "services" upload video and it is then converted.
Bonus: The file size is usually drastically reduced but the video quality has now been compromised by the conversion to Flash Media.
Drawback: The file was converted to Flash Media and your video is now "compromised" by that conversion.
2. Slight advantage by using the QuickTime playback via Web based files:
You (the author) get to set the "control" over they playback (viewing) machines.
There are dozens of ways to get good quality playback and small file size.
http://homepage.mac.com/kkirkster/RedneckTexasXmas/index.html
as an example. Two audio files and dozens of transitions all in a QuickTime container under 4 MB's in file size.
If your files are served via http there are dozens of better html "tricks" to make them do a bit "more".
You must do some more homework or ask a different a different question.

Ah, well, I hadn't actually thought of that one...

While QuickTime is the basis for the MPEG-4 standard, you've hit on a pretty good solution there by serving up MP4 files: Windows Media Player and RealPlayer will at least try to play MP4 files, and the format is QuickTime native. Giving your Windows buddies a lot of ways to play the files, though giving you a little less control over the playback.

The reality is that the ABSOLUTE MOST COMPATIBLE cross-platform format is to store the file as an MPEG-1 video file which almost anything can read. But MPEG-1 is far from the best codec out there and you can do a lot better with QuickTime, or as it appears to turn out, with MP4.

--Dave Althoff, Jr.

To be fair, On2 looks as good as H264, and isn't that different in terms of CPU demands. YouTube use Sorenson Spark, which would compare to Sorenson 3 under QuickTime. It's certainly true that an On2 FLV would look very good and would be immediately viewable to about 90% of Internet users.