I heartily second your recommendation, A Case of Conscience is da bomb. It’s conveniently packaged in The Library of America’s lovely American Science Fiction: Nine Classic Novels of the 1950s set, which itself is pretty much an unbeatably great anthology. LoA folks, it’s time for the 1960s!
