Youtube is designed for live action full motion video. Its compression algorithms assume that you will have continuous frames in rapid succession with relatively small image differences from frame to frame. As a result, the compression reduces the image quality of each individual frame because that loss is compensated for by the inclusion of many other frames and because high fidelity isn't needed to convey motion in the animation. Also, it's not such a big deal since each frame only appears for a fraction of a second and the viewer doesn't have much time to look closely at each individual frame anyway. The compression also depends on the frame-to-frame changes being small so that it only needs to record what's different in the next frame, as opposed to recording each individual frame in its entirety. Audio quality is also reduced because the compression will assume that the emphasis will be on the video's visuals. The list goes on and on.
Youtube does a good job with full motion video because it makes all its compression sacrifices in favor of aspects specific to full motion video. Everything else suffers. Those "videos" which only feature a static image and music in the background (meant to only be an upload of the music itself) sound noticeably worse than dedicated audio files because they rely on that reduced-quality Youtube audio and lack any of the video frames that Youtube intended to compensate the video as a whole with. The same goes for slideshows. A slideshow depends on the image quality of individual frames and lacks some of the compression advantages of full motion video since each successive frame is usually completely different from the last--so each frame does need to be recorded in its entirety. Youtube just isn't made for slideshows.
Your Photostory app is made for slideshows. Since it doesn't have to worry about full motion video compression, it likely uses competent single-image compression (e.g. JPEG) and only concerns itself with successive static displays and the relevant timing, which is quite simple but, again, the type of things that are sacrificed if you instead want to do full motion video.
If you want to put a slideshow online, use something that actually caters to slideshows, like one of shinjixikari's suggestions.
Better yet, don't use a slideshow at all. The slideshow is a relic of film photography invented when someone wanted to display a bunch of photos to a large viewing audience as an alternative to making multiple prints and distributing them. The advantage was the ability to project each image in large format for everyone to see. The disadvantage was that the display was only under the control of the presenter, and not really of the audience. Your typical thumbnail web gallery is much better at the task, as it lets each audience member control their own personal viewing experience (since they decide which photos to click on and when) and still lets everyone see the full-sized version of every photo. Why not just use a standard web gallery instead?
A slideshow (especially on Youtube), aside from being bad-quality, forces the audience to view everything with the order and timing that you dictate. Not much advantage to that unless you're trying to tell some kind of sequential story. Furthermore, it's difficult to internally navigate using a video seek bar (yet another thing which is designed for full motion videos and not slideshows). If someone likes one particular photo of yours, don't you want them to be able to find it and look at it for as long as they want? Youtube makes this task very difficult on the user when it really doesn't have to be.