I made basically the same change about 5 years ago on my 2003 V10 powered Superduty. After upgrading campers to a 32' fifthwheel and then upgrading boats to a 20' Deep V fiberglass walleye boat, I found my truck struggling in the power department. Took it in with about 65k miles on the ticker, had them freshin the trans and swap the stock 3.73s for 4.56s. What a difference! before there was no option of pulling in OD, 3rd was normal and at times 3rd struggled and I had to drop to second. After the 4.56s, I could tow flat land in OD, hills in 3rd and very, very rarely every need to go down to 2nd. Since that time I purchased a larger 15.5k GVWR Cedar Creek and gave up on double towing. The truck handles the new camper exceptionally well and has no issues running down the highway at 65 mph very comfortably in 3rd and when not in the hills or wind, OD works also. I will add that before I swapped gear, I did do the y-pipe modification and also had added a custom tune from 5-Star performance. Those things remained after the gear swap with some updated towing tunes.
If it's primarily a dedicated tow vehicle, the gears are a must have and make a world of difference.