Science fiction is tailor made to discuss big ideas and ideas that are too controversial to discuss in the normal means. The intersection of these two points is religion and because of this, many of the greatest stories and novels use religion as one of their central points. Here are some of my favorite science fiction stories that discuss religion.
The Hitchhiker's Guide to the Galaxy
If the themes of religion in these books were more centralized it would likely be higher on the list but most of the mentions of religion I these books are simply swipes at the ideas something that would bother me if it weren’t so funny. Yet many of the mentions of religion in these stories are devilishly funny. Perhaps the best is at the beginning of most of the books. "In the Beginning the Universe Was created. This has made a lot of people very angry and is widely considered a bad move." He then goes on to discuss how many people think it was created by some sort of God.
The Star by Arthur C. Clarke
Arthur C. Clarke often wrote about religion and his story Childhood's End is one of the best stories about religion but The Star is even more to the point. This is a story about a Jesuit Priest who has went on a trip with a survey team to an exploded star. Something he sees there makes him question his very religion. Any more than that would ruin the fun of the story but if you haven't read it and have any interest in religion you should.
(It's not all that long and the story is here)
Contact by Carl Sagan
After reading "Contact" it is almost hard to understand how so many books that discuss first contact ignore religion. His is a huge part of humanity and though contact with alien races wouldn't necessarily change the beliefs it would certainly impact religion. Although there are other things going on in "Contact" one of the most central themes is religious and what is remarkable is how fair it really is. This isn't Carl Sagan proving religion is for stupid people, it's him thinking about the ideas of religion carefully.
Science fiction is full of stories like these. Some, like "Stranger in a Strange Land" and "Lords of Light" and even "Dune" to some extent involve characters becoming sorts of gods while there are still more that question how the world and the universe came to be. TV and movies also use it well as a central theme in stories like "Deep Space 9" and "Battlestar Galactica" religion comes up often and we will almost certainly continue to see religion in science fiction because the question of God is one that will never be fully answered, and by nature of the theme the best place to think and look about it is science fiction.