1) Gear changes run about $700-$900 per axle depending on your local labor rates.
2) Your owner's manual will tell you the maximum recommended combined weight for an available gear ratio. Note that you may install gears outside of those charts, but you may not be able to easily calibrate the truck's computers if you go beyond factory options. Keep in mind, these are only recommendation, mostly pertaining to performance and longevity.
3) You can print your own sticker if it makes you feel better. Seriously. You don't have a sticker now, and there are no laws pertaining to Combined Weight ratings, other than your combined weight can't exceed the truck's GVWR + trailer's GVWR. You could legally pull 23,000 pounds with a F150 as long as the driver and truck were properly licensed for the load being hauled, and federal bridge limits are not exceeded.
That all said..... going from 3.73 to 4.10 is a pretty minor change. I wouldn't do it for the cost. If 3.73s aren't cutting it for you, even lower gears might be worth considering.
