Which tubes are best is pretty subjective. Depends on what you like tone-wise, how much gain you want, etc.
Pres are a good first route since they're cheaper, less to do (Just swap 'em and go).
JJs and GTs are pretty similar nowadays (I use JJs), Mullards are good, TungSol get a bit earlier of a breakup and sound good.
Rubys, eh. I'm not huge on the new ones, but some dig them.
Other preamp types, like 12AU, 12AYs break up later if you want less gain or can be nice in the clean channel.
Lot of other choices.
You can check out TubeDepot, Tubesdirect and vaccumtube. All have some useful information on each type.