Tube rolling: preamp or power tubes?

What I failed to convey is the usual situation with tube amplification that the big power tube is much more likely to be consumed with use than the small signal tube. Therefore when it comes to finding all the right tubes your chances of finding and affording old power tubes in good condition is typically a great deal more difficult. than finding the best "pre-amp tube."
With 6080 tubes that is not the case they are fairly acessible to most of us. IMHO

I've always begun by doing the output tubes first, in either a preamp, or amp. it just seems right-er to me that way. But I've never seen anything saying which way is best... or the law. I had no 'on hand' supply of tubes either. I might have gone another way, if a bunch of tubes were here in the first place.

they all matter. which ever way one begins... you'll get there eventually.

Picking out the exact or right tube will be far more troublesome than figuring out which ones to begin with... inputs or outputs.

The output or power tubes will have the greatest impact in most circuits. However "everything is important" or "nothing is not important" I think is the correct if quoting Kondo San.
The typical situation is reversed for you and I. For my headphone amp which is a SinglePower "Extreme". The power tubes are also 6080 et al. which can be had for less than a good pair of old stock 6922s.