The lower weight does not reduce the speed, however it does increase how high you can climb.
As you climb it gets cooler (until you get to the troposphere, where the temperature remains the same as you climb. at the poles it's low, over the equator it's pretty high) Above 25-30,000 feet aircraft start cruising at mach numbers in stead of knots. As the air cools, mach 1 becomes a lower speed. So, you're right that as you get higher you go slower.
However, higher up there's less air to cause drag. So you need less thrust - quid pro quo - less fuel. The fuel saving due to lower drag penalties outweighs the lower speed.