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.