What would be the easiest way to build the circuit with a separate power supply for the optos yet still only have one PCB
Just design your board with two separate power planes, and power supply
input terminals.

Separate DC power supply's input to two separate regulators on the same
PCB.

|..P.S. input A.............P.S. input B]
|--[+-]------------------[+-]-----|
|..PIC side........<..out.[]..input..<..| AC connections on outer edge
|.....................<..out.[]..input..<..| optos in center of board close
|..one PCB........<..out.[]..input..<..| to controller ins/outs

TIPS:

Keep AC traces (if any) as short as possible, and located on the far edge
away from the controller side of the board.

Make the bottom layer under the "controller side" a large ground plane with
decoupling caps at all power connection points.

Do not cross-over traces from one side to the other. Noise will couple from
one PCB trace to another right through your PCB substrate.

If you have any mechanical relays on either board, consider MOV's (metal
oxide varistors) across the relay contacts to snub contact spark/discharge.

I've done a number of boards like this without any glitches. All for large
motors & heavy appliances being controlled or monitored by the PIC.

Im my experience, I've noticed that all of the 18F series and most 16F "A"
series are all more succeptible to noise than older non "A" series 16F parts.

a mind of its own and randomy turns on relays, outputs serial data, resets itself etc
That definitely sounds like a serious noise problem, but it may also be the
input you're using. Does it throw a fit if you connect this same input to
any other signal?

Which input are you using?