Susan Howarth’s cycle of novels about the Anglican church.
These are older works, of course, but I’ll mention The Brothers Karamazov and Robinson Crusoe.
You just beat me to it, Primaflora! They do need to be read in order and make for fascinating reading.
War and Peace’s Princess Maria is a very devout Russian Orthodox woman and is a sympathetic character (though some readers want to smack her…YMMV).
Graham Greene’s the Heart of the Matter is about a Catholic man whose fate is directly affected by his religious beliefs. He starts off as a man who just goes along with Catholicism for his wife’s sake, and he becomes much more serious about his faith as the course of events continues. Greene’s the End of the Affair also features a woman who returns to her faith after, well, the end of the affair.
There’s this thing called the Bible…
The Chosen by Chaim Potok (1967) is an excellent story of the lives and expectations of two Jewish boys (one from a Hasidic family and one Modern Orthodox) in WWII-era New York.
The Stand by Stephen King (1977) contains a very sympathetic Christian character in Mother Abagail. The strength of her faith plays a very strong role in the plot and development of several important characters in the novel.
Sharon Kay Penman writes historical fiction based on many real people who were key figures in the Hundred Years War and the Wars of the Roses. Although the books don’t center entirely around religion, it is a very big factor.
Also, Bernard Cornwell’s newer series about the Grail, set during the Hundred Years War, features a main character who is always working out the conflict between his religious obligations and his more nonsecular desires. Excellent books (the first is called The Harlequin).
Most of the characters in **Instance of a Fingerpost ** are religious, for good or evil.
Ken Follett’s The Pillars of the Earth has as one central character a Catholic prior who is deeply faithful, and even battles corruption in the church (set in 12th century England). He’s one of the most interesting and sympathetic characters in a book full of interesting people.
Many of Morris West’s novel involve deeply religious people, like cardinals and popes. I’ve found them really thought-provoking.
This isn’t a recent book, but delphica recommended “In This House of Brede” by Rumer Godden to me so I read it a few months ago. It was excellent, and takes place in an abbey full of nuns. All the main characters are (obviously) women of great faith.
Mark Salzman’s last novel involved a nun, too, although the name escapes me.
MISSION by Patrick Tilley. It’s a serious attempt to address the question of what might happen if Jesus was to return to earth in the late 20th century, how he would be treated, what sort of people he would choose as his disciples, and what might happen to him.
Be warned though, it goes far beyond “mainstream” traditional Christian beliefs, taking in some elements of science fiction and mysticism. But a very challenging and thought provoking read.
Reminds me … I must get it out and read it again. I like to read it round about Lent/Easter time.
Patrick Tilley is better known I think as a writer of mainstream SF - he wrote a series (which I haven’t read) about a post-apolyptic USA called The Amtrak Wars.
Oh that reminds me of another - a wonderful SF story called Let’s Go to Golgotha by Garry Kilworth. A bunch of time travelling tourists go back to see the Crucifixion. Has a chilling, horrific final plot twist.
I’ll second Anne Lamott. Most of her books that I’ve read feature characters who are sincerely devout, but also intelligent and sympathetic. These characters come closer to the Christians I know and respect in real life than do most fictional portrayals.
Raney by Clyde Edgerton features a protagonist who’s a fundamentalist. She has some quirks and faults, but they don’t have to do with her religion. It’s a fun read.
This stuff sounds great! Thanks folks.
The Man Who, I just checked The Brothers K out from the library, probably because you mentioned Serious Sexuality 
I’m currently reading ‘Consider Phlebas’ by Iain Banks. It had one religious human character, and an alien race of religious fanatics.
City of God, and I’ll be damned if I can remember the guy’s name. Very good book.
Lots of good sci-fi deals with religious topics, tho not that many have (I feel) strong religious characters.
Mark Salzman’s book about the nun is called “Lying Awake”, I think.
Isn’t Orson Scott Card a Mormon himself?
Some of my fave books have minor religious characters (in Kristin Lavransdatter, in The Jewel in the Crown).
There are probably some good books about missionaries that we’re all forgetting…like “At Play in the Fields of the Lord”.
I’d second G.K. Chesterton. Good stories are timeless anyway.
And I have a soft spot for Giovanni Guareschi’s “Don Camillo” stories.
(And I’d just like to point out, in passing, that some of us Serious Christians think Serious Sexuality is a gift from God…)
I saw Graham Greene’s The Heart of the Matter and The Power and the Glory cited above. You could add to that his Monsignor Quixote, which is a comedy, but nonetheless about religious characters. Or nearly anything he wrote – he usually had Catholic themes in his work.
Also Brian Moore’s Catholics and Cold Heaven. Catholics is a sort of dystopian satire about what the post-Vatican II Church might become in the future (written before John Paul II), and Cold Heaven is about an initially non-religious woman to whom a genuine miracle happens.
Also see Moore’s Black Robe, about Jesuits involved in missionary work in French Canada/New England in the 17th and/or 18th century (I forget which. It was made into a movie, starring (IIRC) Jeremy Irons.
Anything by James Joyce qualifies. Except maybe Finnegan’s Wake. I don’t know 'cause I could never figure out what the hell that was about.
Charles Williams wrote some religious-themed books in (I’m guessing) the 30s. The Greater Trumps comes to mind. Can’t remember any other titles.
All of the above are quite pro-religion, although Greene especially was certainly aware of the problems of the Catholic Church. He (like me) sees no contradiction between being a faithful Catholic and realizing that sometimes the Church is going to hell in a handbasket.
Not Augustine’s City of God? Not fiction, but after the books of the New Testament, the most important (along with his other work) work in making the Catholic (and probably pretty much any Christian) Church what it is today. Even more than Aquinas.
Jalamanta by Rudolfo Anaya