Forget the encryption; alter the protocol to support overfetching. (Instead of fetching a specific site, you fetch blocks of sites). In a naive version, you'd ask for every site from goodreads.com through to google.com, and then the client would actually visit the site it wanted. In a hardened protocol, I'd imagine you'd use hashing, along with a random salt so that there are many different ways to query the same site.

Right now, your DNS provider has a list of every website you visit (just not how many times you visited it). The shorter the DNS cache, the more closely this list matches your browsing behavior.

This definitely complicates the protocol, whether you put the burden at the resolver layer (needs larger cached) or at the level of authoritative servers (where'd they be effectively cooperating with root servers), but it's the only way to truly safeguard browsing data.