Tips for maximising reliable playback of videos at affordable cost

Hi guys

I'm noticing that the average file size for each of my Captivate videos is 100 - 125Mb. With a fair few course files that translates to a fair amount of bandwidth I have to pay for. Is there any way to reduce this size?

On a related note does anyone have any perspective on servers/video hosting providers that are most optimal for Adobe Captivate in terms of reliable playback at an affordable price?

I'm in Australia but I don't suppose location is so important for server/video web hosting options?

Much appreciated

Hamada