I really enjoy messing around with redstone, so here is my go at my own challenge: (if anybody else has a solution, feel free to also post it - I just posted this to get the ball rolling)
71 Redstone Wire, 15 Redstone Torches
The previous two solutions had a slight glitch with the clocks that caused the chance of the left torch lighting up to be 5/8 rather than 1/2. This new solution uses a 4-clock, ensuring the chances are equal.
53 Redstone Wire, 17 Redstone Torches
Did some rearranging and managed to shave off a massive 5 redstone.
58 Redstone Wire, 17 Redstone Torches
The user presses the button located at the bottom of the schematic, and travels along the two wires squared in green. (The wire goes all the way under the yellow blocks, but the schematic doesn't quite show it.) When these wires are powered, the bottom input of the AND gates are also powered (squared in brown).
The area squared in red is a clock generator (a device that constantly cycles). A wire comes off of the generator, and travels to the top inputs of the AND gates. The inverter (or NOT gate), squared in purple, ensures that the wires coming off of the clock are always opposite.
When the user presses the button, the lower torch on the AND gates turn off, causing the output of the gates to alternate on and off. The outputs are hooked up to the R and S inputs of the RS-NOR latch, squared in blue. An RS-NOR latch can be thought of as a one bit memory cell. The input that last received a signal will stay off until the other input receives a signal.
Because the RS-NOR latch is effectively hooked up to the clock, it will cycle for a second (due to the button press) an eventually stop on either an off or on position.
The output of the RS-NOR is wired to both of the torches - one path going through an inverter (orange) so both torches always display something different.
Here is what is looks like in game: