I'd look first for the 4.11 gears for your existing rear. They are hard to find and you may quickly give up, but since they are the most stock looking and the easiest swap, I'd at least give it a shot.
After that decide if you'd rather deal with changing rears or changing transmissions.
A downside of changing to the T-5 trans is that it is not a heavy-duty transmission. If you actually load this truck I'd suggest leaning toward the rear axle swap. And if you load it heavily you need to ask if the trade off of more speed for less grunt will work for you.
If shifting a 5-speed sounds better than swapping rears go that way, otherwise look for an 8-lug rear that is real close to the stock width and swap. While you need to make sure tires don't rub and that the rear fits under the spring and frame, and the actual width measurement is not as critical as many other things are.
