For what it's worth on gearing, I had a crew cab f150 with the 5.4 and 4r75, with 35s and 4.56 years. It pulled great and I never felt like it was geared too short. When I first put it together, I lived in Kentucky and drove a lot of highways with 80mph limits. When I hauled my slide in camper (around 8500lbs setup I think...?), I was happy to have the 4.56 gears for sure. SO 4.10 will be ok with 33s, but you won't regret 4.30s either IMO. It is really a small difference either way, but personally if I were paying to re-gear I'd go with 4.30s. The 5.4 isn't exactly a power house, and the 4r75 has a tall first gear.
As for the transmission, the 5r110 is much better for sure. There is more to it than just number of gears and ratios. But a decently built 4r75 with low (numerically high) gears with help reduce stress on the trans, and a good tune will help it shift firmer and faster which should reduce heat build up.