Honestly, Tyson being nonreligious might not matter as much as a lot of people think. However, I don't think he'd be the best with messaging, and so would likely have lost to Trump.
Sanders is pretty obviously agnostic or atheist in all but name and Sinema won in Arizona despite not being religious. Tyson's problem would be he's associated with certain stereotypes of atheism as opposed to his actual lack of religious belief.
Honestly, that's a pretty well-reasoned analysis. Even beyond his personal feelings on religion, though, I really don't think Tyson would have what it takes.