I think the SD300 (I have one) does have much better video capability - s500 is limited to 30sec in 640x480 or 3 minutes in 320x240 whereas it is unlimited in the SD300. I think the SD300 also does this at a higher FPS 30 v 15 and also has an ultra high speed 60fps mode at 320x240.
For the size difference, check outSteve's review of the SD300 here http://www.steves-digicams.com/2004_reviews/sd300.html
there is a photo of it next to the s410 which is the same size as the s500.
In terms of pure picture quality the s500 is very well regarded andI think most would say it isbetter than the SD300. Note, if you already have a camera and some memory cards, the s500 takes CF cards whereas the SD300 is SD.
I'm very happy with my SD300 and would certainly recommend it to you. Good luck with whatever you decide.