I think any well-known Democrat who is brave enough to run against Menendez will win the primary and (obviously) the general. Personally I'd like Josh Gottheimer to run against him, but he's a freshman congressman in a Republican district, so I think he's trying to anchor himself for reelection.
If anyone but Trump was POTUS, and Tom Kean decided to run, I could see the state electing its first Republican Senator in decades. I don't see Kean running this year, though.
For what it's worth, Jeffrey Chiesa was a Republican senator from New Jersey in 2013. He was appointed by Chris Christie though.
