To answer the second question first. 26" and 650b are not interchangeable tires, the rim size is different. 650b is a larger rim diameter. Sometimes people swap rims but this will usually only work if you have disc brakes as the pads on rim brake bikes are set for whatever diameter comes with it. There are some exceptions to that but for your question the answer is look to 26" tires.
Tires are a hot topic with everyone having their favorate. Those Nokians are pretty cheap and heavy. For a proven tour grade tire try looking at Schwalbe Marathons as a choice. Others will recommend more.
Cheers.