Suggestions for Improving Home Wifi

For years, I've had to deal with a wifi connection in a two-story home that is perfectly stable upstairs, but abysmally slow (<1 Mbps) downstairs, and I was wondering if anyone had any suggestions for remedying this. We are using a Time Warner-provided router/modem combination device (built by Motorola), so I am aware that a new modem may be a necessity. Should I instead go for a range extender, spring for both, or try something else?