To be honest with you there are a number of ways to answers to that question.
I work on a lot of medical conferences were I am given many presentations with a variety of videos; many formats do work, but many do not, most notably the quicktime container does not natively work in PowerPoint (Though can be achieved with an ActiveX Plugin).
The codecs you have installed also play a factor. However if I do have a problem with a video I either convert it into wmv (VC1 & wma 3) or avi (xvid & mp3), bitrates dependant on quality needed.
Regarding size, that for me is dependant on native resolution of device's display that will be used, the quality of the original and the size of the video will be on the slide. i.e. if I have to play a video on the full screen of a 1024x768 native projector I'd use that size.
It should be worth noting that in PowerPoint 2010 video management has been completely changed, specifically linked videos can be embedded into the PowerPoint file (previously always separate files) and these files can be automatically converted by PowerPoint for compatibility and it converts them into wmv (Though not 100% successfully).
More info: here
I can also mention I use SUPER video converter as it has a simple interface (though many may find it confusing). It allows a lot of format possibilities and it is free and as far as I can tell abides by the L/GNU licences of some of the binaries it uses.