1) Put an optocoupler inside each treat when you modify it.
The H11AA1 AC isolator costs 25c and is AC input i.e. the led input side is unpolarised. If you fit one of these inside each treat across the switch (you still need to get polarity right when you fit it) then the wiring polarity to the opto is irrelevant. Cheap, one part, low on voltage.
You could just use a simple opto in the treat with a polarised plug, so that led polarity is correct.
You could also connect a single opto across two pins of your mcu (A,B), and drive it A hi, B lo, then B hi A lo. Thus it gets triggered no matter which way you wired the led up.
1b) If you want the switch side to be unpolarised, then use two simple optos (Opto1,2 below) (these seem to be 3c from CN) with the leds in series, and the transistors swapped. In this case put the optos on the MCU board.
BTW if you are triggering one treat at a time, then an 8 bit port is able to control up to 56 optos (1b) directly.
2) use an optofet isolator. Not really cheaper than relays, but lower on current, full isolation and no polarity or on-voltage issues.
I personally would go for optos or relays especially if any of the treats are not battery powered.
Bu if you really want to have problems...
a) Since you have to modify each treat anyway, just put a standard 2 pin polarised connector on when you modify them e.g 3.5mm jack, and then they will be correctly polarised when you plug them in. Drive with a transistor.
4) Here's a non polarised switch. You can also use it with optos for Q1 to get a non polarised output. The draw back is the on voltage is 1.4V using ordinary diode bridge, or 0.8V with schottky bridge.
simulate this circuit – Schematic created using CircuitLab