Complexity of hex with random turn order.
You might want to look at the paper "Random-Turn Hex and Other Selection Games," by Yuval Peres, Oded Schramm, Scott Sheffield, and David Wilson. From the introduction: 


  "Random-Turn Hex is the same as
  ordinary Hex, except that instead of
  alternating turns, players toss a coin
  before each turn to decide who gets to
  place the next stone. Although
  ordinary Hex is famously difficult to
  analyze, the optimal strategy for
  Random-Turn Hex turns out to be very
  simple."


So indeed, your intuition was right: this will be in BPP (or maybe P).