If you have the factory limited slip differential, the guy at the shop you talked to may have mislead you. The trucks with the limited slip option in '59 used the GMC Spicer 45 axle with a 3.92:1 ratio (the regular open GMC axle could also be had with a 3:07 and I believe a 4.11 gear) with no option. Parts, other than seals, are virtually non-existant for this rear, there are no gear sets being made as well.
A better way to go would be to consider an overdrive transmission, possibly a T5 5 speed or MY6 4 speed if you want to keep the floor shift. The overdrive gear, coupled with the larger tires, should give you the performance you're after.
