Ok, go get your hands on the space trilogy and read it, the titles you are looking for are Out of the Silent Planet, Perelandra, and That Hideous Strength. Probably my 3 all-time favorite books. Your right about it being more fantasy than sci-fi though.
As far as other books go, I'm totally with you on the old books thing. And the more old books I read, the less I like new ones. Books, unfortunately, have become just another disposable commodity in today’s society. Have you read anything by George MacDonald? He was a big inspiration for Lewis. MacDonald's book "Phantastes" was a turning point in Lewis' life that eventually led to his being saved. "Lilith" is also good by him, as are the "children’s" books "The Princess and the goblin" and "The Princess and Curdiee" which Lewis references in "That Hideous Strength" as "the Curdiee books". Be forewarned though, in regards to the 2 books aimed more at adults, remember, this is mid-late 1800's writing, it is very wordy and overly descriptive by today's standards (beautifully descriptive, but long) this stuff will make LOTR look brief and concise. Might want to try the children’s books first as they are much more accessible.
I might post more later as I have more I could say, but we'll leave it at this for now.