My limited understanding, based on what Justin and a couple of tube sellers have told me, is that I should focus on the input tube (ecc82/12au7) first because that will have the biggest impact. Switching the input tube on the Nautilus did indeed have a huge impact on the sound, but obviously my experience is very limited.
I’ve ordered some power and rectifier tubes too, so I’ll try different combinations.
BTW, if you’re looking for matched pairs, @ProfFalkin has some highly rated 12au7’s at good prices: FS - Tubes!