How about a hash cash based pow concept where nostritches have to Zap the network or a specific relay or something like that to make a post. Cost to post goes up until spam decreases, almost like a difficulty adjustment. Every action (post, like, repost, etc) all has imbedded zaps. It would also be acceptable for a lower tier, less expensive experience that has more spam but costs less (nothing?). In this way end users can specify how much they want to spend and what they want their experience to be like. Could also provide incentive to run relays. Market dynamics would reward most freedom, least censorship, best / fastest relay performance.
I still think relay-based spam filtering is the way to go (some client-based filtering can also help, but shouldn't be the main thing), but there is not a clear way to do it:
One obvious solution mentioned by nostr:npub1v0lxxxxutpvrelsksy8cdhgfux9l6a42hsj2qzquu2zk7vc9qnkszrqj49 that had never occurred to me was that clients should default to fetching replies from the OPs inbox relays and let them decide if they want their reply section to be filthy and full of spam or a nice place.
Discussion
...could a also provide financial incentive to make client applications with elegance, control, and constantly improving end user experience. We may all end up spending $12 / month but based on usage and in a free market of ideas and applications.