I'd say that the fundamental problem here is your approach. You basically want the outside renderer to throw a bunch of random stuff at the wall, then let the internal rendering system sort it out without having any idea what any of that stuff actually means.
Here's what I mean. Consider the case of skinned meshes vs. unskinned meshes. The internal rendering system has no idea which ones are skinned or not; all it knows is that some draw commands use a particular program and a large UBO/SSBO, while others use a different program and much smaller UBOs.
And that kinda works... to a point. And that point is when you're dealing with state values that are no longer encapsulated in objects.
Uniform values are program state. And you might reasonably have two different objects that use the same program have the same value for that uniform. They might have different values for other uniforms, but there would be different variance in which objects use which values.
But here's the thing: in pretty much every case where this happens, someone knows that it happened. And the code that knows that is the higher level code. After all, if two objects have common programs and common uniform values, they probably have a bunch of other stuff in common too. So odds are good that the higher level code knows when such things would happen.
By using this "throw stuff against the wall" approach, by separating the business end of your renderer from the source of that rendering data, you destroy the semantic information you could have used to detect such things. That is, it is the higher level system that should handle the "sort by state change" part, since it can do a much better job.
However, given that you've effectively designed yourself into a corner, I'd say that the simplest approach is to develop a way to encode uniform values, rather than relying on callbacks.
Uniforms can be scalars, vectors, or matrices (arrays and structs use multiple uniform locations). So you need the equivalent of a "variant" type that can store all of such data, of the types supported by GLSL. And then, for each object, you walk through each uniform location in that object's data block and set that value. Sure, "visitation" is not the most instruction-cache friendly approach, but it's a lot better performing than calling a
std::function. At least with visitation, you're executing the same block of code each time.
So what you'd have is a (possibly dynamic) array of uniform data, where each uniform datum is a location, a type, and the variant data. I'll leave the storage optimization of the "variant" as an exercise for the reader.
Generally speaking however, non-block uniform usage should be fairly minimal, dealing only with values that change frequently while rendering with a program. So even in that case, things shouldn't be too bad.