There wouldn't be too much difference initially. Roman commanders under the Republic enjoyed greater latitude in both their exactions and punishments (if you think Pilate or Felix were bad, read up on Verres or Dolabella). So a crucifixion is as easily, even more easily possible. Of course there's no certainty - Judaea may still be nominally independent, the Hasmonaeans fall from grace, potentially Jesus could be tolerated for political reasons, but I doubt it. In the place and time of his life, teaching the way he did invited a lethal response.
With regard to dealing with foreighn religions, the Republic didn't differ much from the Empire. You had general toleration, but an atmosphere of distrust and often a hostile reception especially from the elites. Occasional legislation against what were perceived as threats or abuses could happen, but consistent persecution would be rare. Without the Augustan peace ideology, you might see a few more localised persecutions tolerated, but I don't think it'll make a big difference.
Of course what can't ever happen is the Constantinian conversion. In fact, without the relatively stable and organised pattern of the Empire's administration, I suspect there wouldn't be anything like the relatively unified church organisation we saw emerge before 300. A Roman Republic christianity (disregarding the question of whether the Republic could survive loing enough for one to emerge) would likely look and feel more local and diverse for much longer.