The notion that Christianity depends on "grace" and Judaism on "works" is a terribly unfortunate misunderstanding of Judaism. What divides Paul from Judaism is his insistence that God's justifying forgiveness is only extended to those who accept his Christ faith.
In Paul's thinking, instead of humanity divided as "Israel and the nations" which is the classic understanding of Judaism, we have "Israel "after the flesh" (i.e., the Jewish people), non-Jews whom he calls "the nations," (i.e., Gentiles) and a new people called "the church of God" made of all those whom he designates as "in Christ" (1 Corinthians 10:32).
One thing historians of religions often emphasize is that no religious tradition is a static monolithic entity. Whether we are talking about Hinduism, Buddhism, Christianity, or Islam, the varieties and diversity within each tradition are rich and complex. Judaism is no exception. In the time of Jesus, which historians often refer to as the "late 2nd Temple period" we find within the varieties of emergent Judaism multiple interpretations of almost every subject imaginable -- the nature of God, the coming of the Messiah, free will and determinism, and explanations for the causes of sin, suffering, and evil. At the center of it all was the practical matter of how one is to observe and follow the Torah, or what was believed to have been the revelation of God to the people of Israel through Moses at Mt. Sinai. One of the things we most emphasize in courses on the "Judaisms" of this period is this matter of diversity as we see it reflected in the so-called Pseudepigrapha literature, the Dead Sea Scrolls, Philo, the Mishnah, and other rabbinic writings.
For a general overview of Judaism/s of this period I would recommend a few basic books: Shaye Cohen, From the Maccabees to the Mishnah; James Vanderkam, An Introduction to Early Judaism; Seth Schwartz, Imperialism and Jewish Society: 200 B.C.E. to 640 C.E, and most recently, Daniel Boyarin, The Jewish Gospels: The Story of the Jewish Christ, which questions whether even the adoration and heavenly status that Jesus' first followers gave to him as heavenly "Lord and Christ" was particularly "un-Jewish." I maintain that Jesus was and remained a Jew and never entertained the establishment of a new religion.
In contrast, it was Paul who might actually be called the "founder" of Christianity, with its distinctive theological doctrines. Even though Jews disagreed on how one might reflect and live out all the teachings and commandments of the Sinai revelation, especially regarding what came to be called halacha (literally "the way" or "the walk"), that is how to fulfill the various commandments, in general religious Jews, who took seriously the revelation of Torah, agreed on the obvious point that Israelites of all persuasions were obligated to live according to the commandments in order to be faithful to the Covenant. Historians and scholars seem to be in almost universal agreement that what is called "the Jesus movement," as represented by the teachings of John the Baptist and Jesus of Nazareth, was a movement within the various Judaism/s of its time and is most properly understood in this way, rather than as a "new" religion, separate from the mother faith.
Likewise, I think there is general agreement, as far as I am aware, that James the brother of Jesus, leader of the Jesus movement after Jesus' death, remained an observant Jew himself, based on all our early sources. I offer an overview of the important historical place of James in my book The Jesus Dynasty (chapters 15-17). To be "observant" in this broader context does not so much imply a uniform "orthodoxy" such as later developed within Rabbinic Judaism, but that whatever one's halachic view, one remained "in the camp" in terms of covenantal identity with the Jewish people and a concerted attempt to embody the teaching and commandments of the Sinai revelation.
Judaism, as it developed, was understood as a religion, a people, and a culture, so matters of "definition" could be quite complex, i.e., you could have one who was born as a Jew, spurning the religion, or living immorally, or even turning to another faith, and yet, technically, remaining "Jewish." In the same way non-Jews might take up Jewish customs and observances and still, nonetheless, not be considered "Jews" in a formal sense. E. P. Sanders, in his book Paul, the Law, and the Jewish People, is one of the best summaries of this entire matter. He exhaustively explores the various "Judaisms" of the period, showing ways in which they differed, but also what gave them their essential identity, something he terms "covenantal nomism." Non-Jews, in most of these forms of emerging Judaism, were not expected to "convert" to Judaism in order to have a spiritual relationship with God. They could function within the more universal "Noahite" covenant, and the existence of the "righteous Gentiles" or the "God-fearers" has been extensively documented during the late Roman empire, particularly by my teacher Louis Feldman's work, Jew and Gentile in the Ancient World.
One way of putting this was the adage "The righteous of all the nations will have a place in the world to come." Jesus appears to share this openness to the non-Jew and the messianic vision of the Prophets that all nations would learn to walk in the light of the Torah's essential ethical teachings.
Paul redefined the people of Israel, those he calls the "true Israel" and the "true circumcision" as those who had faith in the heavenly Christ, thus excluding those he called "Israel after the flesh" from his new covenant (Galatians 6:16; Philippians 3:3). He also held the view that the Torah given to Moses was valid "until Christ came," so that even Jews are no longer "under the Torah," nor obligated to follow the commandments or mitzvot as given to Moses (Galatians 3-4). They now have a new "Torah of Christ" that replaces the old Sinai covenant mediated by Moses with a new "Torah of Christ" (2 Corinthians 3; 1 Corinthians 9:19-21; Galatians 6:2). Most historians have agreed that we are not merely dealing with a movement "within Judaism," but the makings of a "new religion" that comes to be called Christianity. This is not to deny Paul's "Jewishness," in the cultural sense of that term. He surely believes in the God of Israel, Jesus as the Messiah of Israel, and the Torah and Prophets as Scripture.
But in Paul's thinking, instead of humanity divided as "Israel and the nations" which is the classic understanding of Judaism, we have "Israel "after the flesh" (i.e., the Jewish people), non-Jews whom he calls "the nations," (i.e., Gentiles) and a new people called "the church of God" made of all those whom he designates as "in Christ" (1 Corinthians 10:32).
This does not mean that Paul advocated immoral living, he surely did not. In all his letters he takes pains to enforce and reinforce the essential ethics revealed in the Torah as applicable to Gentiles upon his followers. The rub comes for Jews -- if it is now okay for a Jew who is "in Christ" and thus part of this new spiritual Israel, to fail to circumcise his or her children, to ignore observance of the Sabbath and the festivals, to eat anything set before them, and to generally "live as a Gentile" in terms of observing such marks of Torah observance then Paul's position takes him outside of "Judaism" or observant Torah faith. Such a view implicitly leads to the abolition/replacement of the mother faith. It was upon that basis that the entire super-sessionist/replacement idea that became so current in Christianity developed. Paul takes the position in Romans 9 that any Jew who does not share his faith in Christ is "lost" and cut off from God, no matter what might be his or her spiritual devotion, Torah observance, or even reliance upon the grace of God.
In recent times Lloyd Gaston, John Gager, and Krister Stendahl have argued that Paul's "abolition of the Torah" was only directed to those in the Jesus movement who sought to force Gentiles to convert to Judaism. I am convinced that they are wrong. The late Alan Segal, in his important study, Paul the Covert: Apostle or Apostate, successfully demonstrates that Paul's message does indeed represent a departure from any standard from of what might properly be called "Judaism." Boyarin and others are certainly correct to question whether there was a "religion" called "Judaism" in this period, prior to "Christianity" over against which it came to be defined, but certainly one can speak of Jews and the Jewish people on a sociological level, which includes aspects of Jewish cultural identity and observance of Jewish customs associated with the Torah.
Then there is the more "theological" the matter of "justification by faith." Judaism in all its forms has taught that all humans are sinners and can only be accepted in God's eyes through repentance and faith. Psalm 51 would be the most classic expression of this, the Thanksgiving Hymns in the Dead Sea Scrolls reflect the same for the Qumran community, as strict was they were in their legal interpretations, and Rabbinic literature reflects the same. As a Jew Jesus expressed these very ideas when he speaks of the two men praying in the Temple, one of them a "sinner" who smites his breast and turns to God, and is thereby "justified," and the other self-righteousness, thinking he had no need of justification (Luke 18:9-14).
E.P. Sanders' study on Paul make it clear that the notion that Christianity depends on "grace" and Judaism on "works" is a terribly unfortunate misunderstanding of Judaism. What divides Paul from Judaism is his insistence that this grace bringing justification is only extended to those who accept his Christ faith. With these three elements based on Paul's perceptions and heavenly visions: a new definition of Israel, the abrogation of the Sinai covenant, and the restriction of God's grace to those who "accept Christ as savior," we truly have a "new religion" and by no theological, cultural, or historical definition could it properly be called "Judaism." And certainly Christians until our more recent ecumenical times would say "and rightly so!" Historic Christianity of all stripes and descriptions has embraced its replacement theology with pride and a head held high.
Paul is truly the hero of this way of thinking and only in recent times have scholars tried to "redeem" him from his own words in an effort to make him more politically correct vis-a-vis notions of ecumenism and tolerance. Countless books have been written in the past hundred years arguing that Paul is the "founder" of Christianity, sharply distinguishing him from Jesus. Joseph Klausner's, From Jesus to Paul is one of the first and is still worth a close study, but many others come to mind, Albert Schweitzer, The Mysticism of the Paul the Apostle, Gerd Lüdemann, Paul the Founder of Christianity, Hugh Schonfield, Those Incredible Christians, and Barrie Wilson, How Jesus Became Christian, to name a few. My own new book, Paul and Jesus: How the Apostle Transformed Christianity explores these and many related questions. Most important, I see to place Paul in the broader spectrum of the religions of the ancient Mediterranean world as systems of divinization against the background of a dualistic Hellenistic cosmology but within that world I see him decidedly as laying the foundation for a new faith distinct from Judaism in its various forms.