Another thought-provoking question Jacob, and sadly one I missed until today. After only brief consideration I think perhaps what you want can be done more simply but I look forward to your critique of my proposal.
Assumptions:
- Exact preservation of the structure of option lists is not required
- The specific order of options is not significant
- Option rules may be safely evaluated
Basic Proposal
SetAttributes[setOpts, HoldFirst] setOpts[head_[args___, opts : OptionsPattern[]], new__] := First /@ GatherBy[Flatten@{new, opts}, First] /. {op___} :> head[args, op] Test:
setOpts[f[1], q -> r] f[1, q -> r]
setOpts[ f[2, q -> b, z -> x, {aa -> bb -> cc, foo :> bar}], z -> dog, a :> cat ] f[2, z -> dog, a :> cat, q -> b, aa -> bb -> cc, foo :> bar]
setOpts[Plot[Sinc@x, {x, 0, 10}], PlotStyle -> Red] 
Extended definition
To make the following case work an additional definition is required:
delay := Plot[Sinc@x, {x, 0, 10}] setOpts[delay, PlotStyle -> Red] setOpts[delay, PlotStyle -> RGBColor[1, 0, 0]] (* failure *)
I shall use the same method I did for:
- How to achieve Set+Part like behaviour in custom Set function?
- why set values in this way doesn't work?
- Creating a Block from a list of rules
whichThis will require my step function from: How do I evaluate only one step of an expression?
SetAttributes[step, HoldAll] step[expr_] := Module[{P}, P = (P = Return[#, TraceScan] &) &; TraceScan[P, expr, TraceDepth -> 1] ] setOpts[other_, new__] := step[other] /. _[x_] :> setOpts[x, new] Now:
setOpts[delay, PlotStyle -> Red] 
Related:
- Consistent Plot Styles across multiple MMA files and data sets
(setOptstherein is not the same as the one here)