actually...
I tried to watch a .mov file embedded on a webpage and it wouldn't load. I tried it over both EDGE and wi-fi connections, but no dice. Last time I checked, .mov files are Quicktime compatible, right? I believe H.264 (the encoding for Apple's iphone-specific movie trailers) is the one and only video format that iPhone's Safari will load currently.
As for videos synced to the iPhone through iTunes, I imagine .m4v or .mp4 will both do fine.
(this is all based on using my friend's iPhone, btw, I haven't gotten my own yet.)