Slow Streaming Issue

I have created a website where people have to paid to be a member to view the video content by video streaming.

However the streaming speed is extremely slow and the hosting company said I need to encoded to run on sever streaming but I'm worry it might compromise on the video quality.

Currently for this video I've encoded, the video is set to WMV with file size 8.67MB and 360x270 for frame size, Bitrate 653, and duration is 2min and it take almost 10 min to buffer and load before it start playing. And that's the same to the rest of the video, some might even take to half an hour.

What can be done the most economical to solve this problem?
CDN?
Dedicated Server?
encode in Flash Player?
Or others???


Please help!!!!