This is veyr similar to why I still attend the church that I do (and have for 30 years, since I was a kid - I disagree with several of their beliefs (which is part of the reason I will not take oiut membership) but the church as a whole is great and I enjoy it. I also think that going to a church that I disagree with some of their doctrinal statements on challenges both me and them, as I see it foolish to engage in a healthy factual debate (which I know all Dopers love to do 
) with a church where you agree with everythign they believe! As long as they’re cool with you not having to agree with everythign they agree with to worship there, and you’re cool about attending such a place, you may find it beneficial to exercise your debating skills with them (at appropriate venues, of course) in friendly discussions with elders and pastors.
I was a convert to Christianity four years ago and I spent a considerable amount of time church-shopping. Two things quickly became apparent to me. First, the number of different churches out there is much larger than what you’d guess if you got your information from mainstream sources, and second, most denominations present a more unified face to the outside world but contain substantial differences on the inside. So as you begin exploring, I would urge you not to rule out churches that might be right for you. On the other hand, there are a few that you probably do want to avoid for being too right-wing; I’m thinking of Primitive Baptist, Seventh-Day Adventist, and LDS.
I remember thinking early on that I definitely had no interest in ‘High Church’ denominations with a strong ceremonial focus, such as Catholics, Russian Orthodox, or Episcopal. Now, though, I’ve started to see that the focus on ceremony, ritual, and liturgy* all contributes to knitting the congregation together is a spiritual way, and thus helps people with clashing viewpoints on theology or politics still work and worship together. As I’ve understood that, I know feel more at home with that sort of thing, and in fact I’m a member of an Episcopal Church at the moment. (I was formerly Methodist.)
Another possibility that you might look at is the Emerging Church, which would be better described as a movement than a denomination. Generally they are small, local groups who usually do not have a church building or a professional clergy, but instead meet in homes, cafes, or just about anywhere, and are less organized than a formal church body.
When you enter a new church, don’t be afraid to approach to tell people that you’re new and that you’re looking around for a church home. People will be friendly and inviting. Also, don’t be afraid to speak to the minister directly, and to ask him or her for a one-on-one meeting. They’ll usually find time to do it, and if not, they’ll at least send somebody who can meet with you.
Lastly, I will recommend some books as well. Orthodoxy is the autobiography of G. K. Chesterton, describing his conversion from agnosticism to Christianity. It’s wise, witty, and you could probably read the whole thing in about an hour. A Guide for the Perplexed, by E. F. Schumacher, is a quick and readable introduction to a modern philosophy of religion. And Confessions of a Guilty Bystander, by Thomas Merton, is the daily journal of a monk who was perhaps the greatest spiritual writer of the 20th century.
*In case anyone doesn’t know, “Liturgy” is Christian-speak for the formal list of prayers and scripture readings used by a denomination.
Another church shopping reference, Mystery Worshipper. It has a definitely Anglican bent. But someone might have reviewed something in your area and I like their list of questions.
I go to a Vineyard church, and that might be a good place for you. The churches can vary quite a bit from place to place, but they tend to be nonformal and low-pressure. They often have small groups, and I’d recommend checking some of them out and finding one where you like the people and fit in well. Finding a good small group might be better than joining an actual church.
They’re involved in social justice. How liberal they are depends on the pastor and the people there. My church has a mix between conservative and liberal members. The head pastor doesn’t comment on politics but says he always votes for the candidate that he thinks will do more for the poor, and sometimes that’s from one party and sometimes from another. The associate pastor (who I’m good friends with) is quite liberal and he’s upfront about it.
If you’ve ever seen the movie I’m Not There there’s a scene at a Vineyard church that’s pretty accurate, although the music is not as good as in the movie.
This is neat. I just signed up. 
I mostly lurk around here, but I just wanted to say that I am praying for you.
I was also raised Southern Baptist and lived my youth and young adulthood very firmly planted in the thou shalt nots: good Christians don’t dance, don’t cuss, don’t smoke, don’t wear pants to church if they are female, don’t have anything but a paino or maybe an organ if you are “progressive” in your services. I got so tired of being bored in church. I got tired of being expected to go to services three times per week. I got tired of the rules. This works for many people, like my mom for example, but I needed something different.
Jesus Christ was only about two rules: love God, and love each other. Once you go back to that, then everything else is man made fluff. Once I realized that what’s most important goes on between me and God and me and my neighbors, then it became clear that my religious upbringing was not for me.
When I found the non-denominational church that I attend now, I felt like Dorothy opening the door to Oz in her black-and-white bedroom. I love going and they encourage me to get closer to God and to serve my fellow man. I hope you can find a church in your area that does the same for you. Going to church is not really necessary to have a personal relationship with Jesus, but it helps you recharge and focus.
You guys are all so wonderful with your advice! Thanks everyone, I’ve been reading along raptly and love hearing about your reconciliations as well. Perhaps I should start another thread asking for stories about folks coming back to their faith… hmmmm. Anyway, I’m definitely going to be checking out some of these church and book suggestions. I also appreciate the prayers and sweet lurkers stopping in to help. You all rock!!