I liked Second Foundation by Isaac Asimov. Yes, that’s Part 3 of a trilogy(*) but I liked it best and reading the books out of order shouldn’t hurt much.
(* - actually a heptology or some such by now, or even worse if you count the post-Asimov Foundation novels.)
The problem here is that the series sucks hard-core. Gateway is ok, but the rest…<shudder.>
Zelazny is an interesting suggestion. Doorways In the Sand is a nice, light romp. So is …And Call Me Conrad. I’d hold Lord of Light for a later suggestion.
The Warrior’s Apprentice, by Lois McMaster Bujold. Characters you care about, especially the hero, in a wonderful coming-of-age plot. Plenty of humor and pathos, too. Also, once you’ve read it, you can read the rest of the series.
(Yes, I know it’s not the first book in the series, and it has spoilers for the earlier books. I still think this is the place to start.)