As the common rails go, 04.5 and up got a little worse mileage than the 03-04. On mine, I got a consistent 21-22 everything stock. Got smarty and as long as I babied it, I got as much as 24... still everything else stock.
I've run just about every smarty tune that Marco released at one time or another. The only real constants I have found is there aren't any. Every tune and every setting seems to behave a little differently on every truck. So you have to play some. What I have found for myself, is that the higher level tunes, (sw 5 and up) do better than the lower ones. Run as high a timing as you are able safely to. My best mileage came on the old Beta 4.4 sw7, which is a hot tune. That is the only tune as well that I have dyno'd that got me more power on sw7 than sw9. Many others though get higher results on sw7 than 9. That said, my best tuning to date (thanks Marco for taking the time with me!) sees sw8 as the highest powered SW. That is for me, others may differ.
I used to switch tunes all the time to get better mileage or better power dependent on my situation. Now I just leave the TNT-R on all the time. And my current mileage is much lower than the 24 I got in the past... big stix do that...
There is significant mileage gains to be made with tires and pressures. What I found was the best compromise was 285/70/17. It improves the gearing enough to drop rpms on the freeway without adding too much in rolling resistance and weight. There is a catch 22 there. The 35's are hurting you.
Good Luck!