I haven't used them, and found them only from a google search, but what about hosting the videos with someone like this:
You can at least try them for free it would seem.
I think streaming is the way to go, or look into reducing the size of those files. On decent websites you rarely see video 'downloads' though - always tends to be streaming in my experience. Your own web site host might also do streaming hosting if you ask them.