A couple that were pretty mind stretching for me were two by John Brunner, "The sheep look up" and "Stand on Zanzibar" which are both dystopian, the first focusing on environmentalism and the second focusing on the source of violence in our day to day lives. But really, I'd suggest anything by him. He's really great at writing a good story around two or three ideas. I'd contrast that with Huxley and Orwell, who always feel like they're beating you over the head with the ideas they want you to assimilate.
Also, Starmaker by Olaf Stapledon is a radical imagining of alternate lifeforms, and civilizations and intelligences. It ultimately ends up being a bit religious, but its purely speculative and not at all dogmatic: it proposes the existence of an immature creator who creates an infinite sequence of universes, with there being greater complexity at each step. One of the universes that is imagined has two orthogonal time directions, just to give you a taste of how far out the journey gets.
Magic space feudalism is therefore a viable idea.