Your description of Malone Dies reminds me of Notes From Underground by Dostoevsky. I found it hard to get into at first because the prose was different from most books I've read (might be the translation, but the Narrator is also crazy). After starting and restarting the book a few times to get into the flow, it definitely turned out to be one of my favorite books.

Also, for sci-fi I'd recommend Hyperion by Dan Simmons. This is the first in a trilogy but can be read and be satisfied with not reading the other two (although the second one, The Fall of Hyperion, is very good).

I read the first (Hyperion) one on a recommendation and I think the guy who recommended it to me was also read it based on a recommendation. It makes me wonder what the longest "recommendation streaks" are and what books they could be for.