See, the problem is that I don't really
know what I'm looking for. I agree with the poster that suggested staying clear of TV show tie-ins, I know enough about literature to know that I really need to read 'proper' books!
As for what I read now, I actually don't read novels much - I do read a lot of books connected with my job. I'm also currently doing a part-time MA. The point being that reading a supposedly 'deep' book doesn't really faze me because (with bragging) I'm reasonably intelligent. So, there's no need to 'wean me' with books that are written for children
In that case, the ones I suggested certainly should fit (as should many of the other suggestions here). Each of these has been read and praised by those outside the sf fan base, as well as those within (each of them has won awards within the community, for instance); each has been viewed as a worthy contribution to general literature, for that matter.
As for the religious element, either
A Canticle for Leibowitz (Walter M. Miller, Jr.) or
A Case of Conscience (James Blish) would fit the bill -- both are quite intelligent examinations of fundamental religious issues, and both -- though coming from quite different camps -- treat the entire idea with respect as well.
Flowers for Algernon (Daniel Keyes) has proven quite popular with both readers of "mainstream" and sf, which is one of the reasons I suggested it. It's a beautifully written novel (one can say the same for the original short story as well), with a great deal of depth both emotionally and intellectually. I'm rather dubious of the idea of not suggesting a book because it doesn't fir the stereotyped preconception of sf, if for no other reason than a great many of the best books in the field step far outside that straitjacket. It
is sf, but not space-based nor techno-based. It takes one extrapolation of (medical) science and explores its effect on an individual and those surrounding him. A very poignant book, all told.
Where Late the Sweet Birds Sang is a bit difficult to sum up, save that it tackles (or rather, tackled, as it was published in the 1970s) many of the major issues we're faced with today, and does so with both grace and style. Kate Wilhelm is an exemplary writer in many ways, and this book has also long since transcended the genre itself.
As for the Dozois anthologies -- I merely suggest them as a single-volume concentration of a wide variety of newer material. The same with the Hartwell (though it must be admitted the Dozois volumes contain much, much more).
As far as the futuristic, space-based (as well as having a fair amount take place on Terra), but intelligent adventure novel full of ideas, I'd agree wholeheartedly with
The Stars My Destination (Alfred Bester). A pyrotechnic performance, but one which has remained a classic since its first publication. Then again, I'd also suggest several of John Wyndham's books as well....