I think you should opt to replace speakers first, then the receiver. The reason is, most subwoofers that come with HTiB systems are passive, so they need to be powered by the main unit. Most subs you buy separately are active, meaning they need a low-level signal (as they are self-powered).
I think the best thing to do for movie watching would be to find a center channel that you like and replace it first. It will clean up the dialog as well as most of the sound you hear in the movie. From there, repace the L&R speakers. After that, replace the receiver AND the subwoofer. The surrounds should be your last investment, as they get used the least in a movie.
What kind of budget are you looking at for this first step?