Well there are many webhosting which includes the features for video hosting. Depending on the budget you have you can choose the webhosting.
Depends on the quality and size of your movies, youtube if they're small and vimeo for very hi quality vids.
There's a way around this, you make a couple minutes of blank at the end, or just stick it on an image or something, this way those videos don't pop up
Blip.tv has all those options too (when it comes to branding private videos). They provide a direct .flv URL which you can use with your own player (e.g. JW FLV Player) as well as the original format of the video you uploaded (e.g. .mov, .mp4...).