The Choir of Kings College Cambridge - http://www.amazon.com/Loved-Hymns-Choir-College-Cambridge/dp/B00005...
If you dig the men and boys sound.
For hymns specifically from the Anglican tradition, look up the choral works of John Rutter. For an American hymnody, look for anything by Bill Gaither. Might also look for some Hildegard von Bingen, for Chant from a femenine and Germanic perspective. Not really sure where to find recorded Lutheran hymns. Oh, and one other, check out the Blind Boys from Alabama for stuff from an American Southern tradition.
Given that he died today ... Andy Griffith comes to mind. I assume his hymns have been released on CD.
Might also look for some of the compositions of Dr. Z. Randall Stroope. He's head for the Choral Department at OSU. I have had the good fortune to sing under his direction, the man knows how to arrange old American hymns and keep the sense of the musical line. He's good!
My iPod is sick at home, or I'd be all over this.
Because I acquire hymns mostly by liturgical season, I mostly get them hymn-by-hymn from iTunes. Everything everyone's talking about here is available on iTunes.
For Psalms, look up Tallis.
Also, our local public library system has lots of "Christian" music - chant, oratorios, hymns (especially those with a Celtic or -can I say- Negro character). It's a great way to sample genres and artists before you buy. If you have access to an academic library, they will have a bigger collection. My university had online access to the entire Naxos collection, and I think they extended that perq to alumns, but I never set up the log-in information.
Gaither Vocal Band or even the homecoming gang do some really good ones