I'll throw some positive vibes for yah. I had a 4 sp 03 Avalanche with a 5.3. Went from a 3.73 to 4.10. I can tell you it definately helped pull our RV. Took cruising RPM @65 mph from 2.9-3k to around 3.3k. This was more inline with the 5.3 power band. Helped on launch with camper allowing me to get up to speed a little quicker. In the hills it helped me stay in 3rd and did not have as many down shifts th 2nd gear. If you have a 6 speed I would think the results would be even better. More gears to play with in the hills and flats.
To correct the speedo I bought a Diablo tuner. Allowed me to reprogram for the speedo and I was able to get a basic trans and engine tune. Didn't care so much about engine, but really want a tow tune that would quicken the shift points and hold 1st & 2nd longer so I could get up to speed more efficiently. Only drawback was the MPG.
One last thing if your computer shows different speeds front and rear, this implies you have 4wd, if so you need/should have replaced gears in both axels, I did on mine.