Long tube headers!!!!!!! take it from us. You can have both a cake and eat it. The trick is not using the gas pedal too often. the long tube headers are going to give you more power due to a scavaging effect due to the design of the long tube headers. At the same time, because the scavaging is occurring, you are getting more fresh air into the cylinder, allowing for more complete combustion and more power. Since you are cruising at a constant speed, the power needed to keep the truck at a certain speed is constant, you can burn less fuel because the cylinder is burning more completely, getting more power out of the same amount of fuel.
Now, you decide to use the loud pedal a lot, you can plan on single digit mileage too. This is where self control comes into play.
Another thing you may want to consider is switching over to e-fans. This isn't the end all modification, but by getting rid of the mechanical fan and going over to e-fans, your motor will warm up quicker (which will get you out of running the motor rich sooner), you will have less losses from loads on the belt (no more fan producing drag), and you will see on average about a 6 hp gain along with 8 ft-lbs or torque gain (across the whole RPM band, not just at one end). But, like I said with the headers, you get what you pay for. I've seen guys cheap out on their systems and after a year or so, they start having fan issues which then leads to overheating. If you want to learn more about this, let me know. I've been down this road.
Also look into the "Gotts mod". takes a little bit of time, but if done properly, can net you some power for free while improving the mileage of the truck (any questions, just ask).
Another thing that I would tell you to look into is modifying the air box. This is something I did and tested it on a dyno. All you do is you remove the funnel portion of the air box that goes between the metal band that joins the two halves of the air box and the fender. I netted 1 hp and 10 ft-lbs of torque. Big numbers, by no means. BUt, in this case, every little bit helps.
Between a combination of modifications that I have done, I am still able to maintain 13 mpg running 37" tires.