If money isnt an issue, go diesel. It is for me, so I'm going to hang on to mine.
Do the math and see if it makes sense, if you're unhappy pulling 3.5k, it wont be any better with 15.
If you were going to keep the truck, maybe headers/y pipe if you have stud issues, a quieter muffler, and lock out OD for everything but flats. 4k rpm in 2nd should get you 50+ mph or better, and should pull 3.5 k fine, just dont let the rpms die before you decide to let it wind.
For me there are times for OD, OD off, and just pulling it down to second, the more practice I get, the better it goes.

 

Thanks to all of you that replied to my original post. I appreciate all the tips; over the past year and over 12k miles I've tried all the tricks. I agree that I started off on the wrong foot with the 3.73 gears and the slightly oversize tires, but it should have been a monster puller to me with my lightweight trailer, and it simply wasn't/isn't. I pulled the same trailer with my Jeep Grand Cherokee (yes, it did have a tow mode) with a 4.7, and it did the job at least as well as this thing does, except for the steepest grades, and with 3 mpg better economy. I bought the truck with the intent of being able to tow a 5r of at least 10k lbs dry, and it's simply not possible with this setup as it is. I'm unwilling to invest a huge amount of $ in gearing, etc. to see if it is going to be 'ok'. I'm going to look for a Ford diesel that hasn't been abused and will get it checked out completely by a good diesel mechanic before buying. I still like the truck very much, but 'Black Bart' will be going to a new owner soon. I've been babying all my rigs for more years than I'd care to mention (have been retired for 5 years now), so I'm expecting good things. I've owned another diesel for many years in the past and just loved it, so I'm expecting the same again. Cheers.

 

It is not really an issue on the east coast or mid west but out in the western part of states you get into higher altitudes, it can have a drastic effect on power output on a naturally aspirated engine regardless of fuel type. Forced Induction engines like the PSD will be affected quite a bit less by the thinner air at higher altitudes and thus do not lose as much power.

This article gives a rough idea of the loss. THE AFFECT of ALTITUDE on VEHICLE HORSEPOWER - Yahoo Voices - voices.yahoo.com

 

You say "if money isn't an issue, go diesel". Can you elaborate?

 

I made a 200 mile trip today pulling the same 5500lb. 20' trailer that I normally pull with my 7.3 Excursion. Mostly flat ground, but there are 3 really good hills.
This is only my secound time pulling with the V10. The last thing I towed with it was my 29' TT, but I had never towed the TT with the Excursion. So in other words, today was the first time I have been able to do an exact load comparison between the F250 and the Excursion.
So here is the outcome: Flooring it from a red-light the V10 is faster, on flat ground just motoring down the highway 65-70 again the v10 does it more effortlessly, On a good hill the V10 needs lots of throttle where the 7.3 will take it with ease. When I refueled the F250 got 9.09 miles to the gallon where the Excursion gets mid 14.