Hey, @Sanjuro77 and welcome to Midihub forums!
Your ideas are all good:
in your parallel Program Change line, you might want to Transform-Replace the Note On with a Note On with fixed Note# so a following Random pipe (Parameter = Pitch (semitones)) gives the same range of PC outcomes with a later Note On → PC Transform.
If you decide to Delay the Notes remember that Delay has fixed Length.
The work around for that is here.
for this I’ve found 2ms works on my gear; yours may vary.
Sounds like a good PatchStorage edition 