The Book of the Weird by Barbara Ninde Byfield periodically comes to my awareness, but this recent post by perdustin finally made me quit procrastinating and order it. Head over there and read the post, but suffice it to say, it's just as charmingly pre-D&D as I had hoped. Well worth the time to track down.
Star Barbarian and Lord of Blood by Dave Van Arnam form a science fantasy duology. I haven't heard much about them (I was drawn them by the title of the first and the Steranko cover on the second volume.)
but check out this cover blurb on Star Barbarian:
Centuries before the multiwave-drive ships had come to Morkath of the Caravan Stars--bringing colonists, empires, confederations of plunderers. Finally, the planet was exhausted and left to descend into barbarism.
Now, savage tribal leaders fought over the blighted lands. Among those warriors was the young hunter Jamnar, who vowed to reclaim Morkath from the demonic powers that gripped it--the dark god Shaphath, the priestesses of Astaphar, the evil priests called Kvununun...
The mighty Jamnar would have aid in his quest. Prosperon, the interstellar castaway, would lead him to the forbidden temple of Telshasoth. But only if Jamnar himself dared to enter the temple's portals--and therein seize the 3000-year-old secret of a lost civilization--could he hope to save his people and a planet plunged into infamy and terror...How could I pass that up?