I like the idea of providing an RSpec shared example to test all these behaviours.
For the constructor, I would change "consider using keywords" to "should use keywords". Keywords should be the default, unless the order is really obvious.
Re: "Value construction options could be provided by keyword arguments." I would probably prefer value contruction options to be in separate class methods, instead of #new.
Re: caching. I would be hesitant to do this at the global level (e.g. stored in the class). If the cache never gets flushed, it could eat a lot of memory.
Re: freezing. This is good for basic types like strings/arrays/hashes, but I would not recommend freezing complicated types (i.e. custom classes).
Re: #merge.
I like the name #merge, although I usually use #with.
Re: [each, of, structural, elements].map(&:hash).hash
I don't think the .map(&:hash) is necessary. It could also be to_h.hash in most cases.
I went through the values gem and some of my own code to see if I could add anything, but I couldn't find anything extra.
So I give these convetions a 👍