So your truck is an F-250 with a 6 inch lift and 35's?!? IMHO, a 5.0L is not a great engine for a truck that is going to be used for a truck, but it's definitely nowhere near enough motor for that kind of a truck. It's not surprising that it's starting to hammer. A 4.9L 6 cylinder might be OK, but I actually think you'd get better power and fuel economy with a bigger engine. A 5.8L wouldn't have to spin as fast or work as hard to move that much truck around, plus it can bolt in place of the 5.0L. The 6 cylinder would require changing the riveted-on frame mounts. You'll have to change the computer regardless of what engine you go with if you go back in with anything besides a 5.0L, but at least the wiring harness itself would be the same for a 5.8L. Unless the truck is particularly nice or you plan to personally put another 100K miles on it, I wouldn't be looking at a new or remanufactured engine. For the $1000 you're looking at spending on that, you could find an entire truck with a good 4.9L or a 5.8L and have everything you need to do the swap.
There's no reason to be scared of the swap. It's a piece of cake. The '95 351W will be an excellent engine for your truck and I think you'll be very happy with it. It will bolt right up to your engine mounts and transmission. You may need to use the accessory mounting brackets for the 351W, though. Make sure that they get left on as part of the deal when you buy it. ONE EXCEPTION - You cannot use the flywheel/flexplate from the 5.0L on the 5.8L. It will bolt up but it won't be balanced correctly and the engine will vibrate. You'll need to use a 28 oz. imbalance 164 tooth flexplate from a 351W or pre-'82 302. That's the only part that won't work. You're also going to need a new computer. Get one from an '87-'91 truck with a 5.8L/351W. It will swap in place of yours and work fine with your existing wiring harness and the new engine.
If your truck currently has an E4OD, then you're going to need a computer out of truck that had a 351W/5.8L and an E4OD to get both the engine and transmission to work right. Send me a PM if you have trouble finding one. I happen to have a spare sitting around here for just that very combination and I know it works. It came out of a '90 E-250 Econoline van. I can make you a deal on it.