Hey!
This sounds great.
As a general point, I think it makes sense to fully complete the ICDevs bounty first, and then we can worry about merging into base.
By QOL, I mainly mean adding extra utility functions (e.g. motoko-base/Buffer.mo at master · dfinity/motoko-base · GitHub). I don’t think there will be as many functions for maps, but things like finding max value, min value, folding over maps, mapping a higher order function over the kv pairs, producing a text representation of the current entries, etc.
Serialization seems to be the most thorny problem. Right off the bat, do you think there’s a good way to have a non-stable version, where the user doesn’t have to pass in a memory (since it’s just stored in the normal heap), and there’s no max sizes or converters since serialization is not necessary?
As for the stable use case, I agree that having the users pass in the converters is the best approach at the moment. I would definitely not implement every combination of serializer by type 
A possible alternative: Not sure if you’ve considered using to_candid and from_candid primitives? These are Motoko operators that let you serialize any shareable type to Blobs and back. Could be useful as an out of box serializer, except for the fact that you need to convince the compiler that the generic types are shared. As far as I can tell, this is a bit tricky at the moment. Motoko Sharable Generics.