Coin Arrangement Puzzle Disclaimer: I'm not sure how math related this puzzle is (it could potentially be), but I thought it was an interesting puzzle, and I also don't know how to solve it so I wanted to see if anyone had any ideas. 

You have a board divided in quarters and a coin is in each spot. You
  do not know whether each is facing heads or tails upwards. In each
  turn, you can choose flip any number of coins. Specify a sequence of
  turns that guarantees that at some point all coins will be facing the
  same direction.
Follow up: Between each of your turns, the board is rotated an arbitrary
  amount amount (90, 180, 270 degrees). Specify a sequence of moves that
  guarantees that at some point all coins will be facing the same
  direction.

 A: For the follow-up you have to assume that success will be announced after each try if you manage.  We assume that a malevolent adversary controls the rotation, but you can flip a single coin, an opposite pair, or an adjacent pair at your option.  You just can't keep track of anything except relative position between flips.  You start knowing they are not all heads or all tails.  Flip two opposite coins.  If that doesn't work, you either have an odd number of heads or two adjacent heads.  Flip two neighboring coins.  If that doesn't work, you either have two opposite heads or an odd number of  heads.  Flip two opposite coins.  If that doesn't work, you have an odd number of heads.  Note that so far, we have always flipped an even number, so the parity hasn't changed.  Flip one coin.  If that doesn't work, you have two heads and two tails.  Flip two opposite coins.  If that doesn't work, you have two neighboring heads.  Flip two adjacent.  If that doesn't work, you have two opposite heads.  Flip two opposite.  Guaranteed to work.
If success is all heads instead of all the same, put flip all four at the start and after every step of the above.
A: Take the top right corner as fixed. you'll be flipping the other 3 coins to match it. The idea is that these 3 other coins can be thought of as a binary sequence. numbering them as $1,2,3$ (in any order), assume they start at zero and do moves that make you count from $0$ to $7$ in binary. so:
(0)   000
flip 1 (1) 001
flip 1 flip 2 (2) 010
flip 1 (3) 011
flip 1 flip 2 flip 3 (4) 100
...
and so on. Gray codes would work here as well; anything that will take you through the sequence. Since you enumerate all combinations of flipped/unflipped, one must involve all of them facing the same way.
My first guess would be that no solution exists in the case where the board is moved at random, since it seems entirely possible (though unlikely) to end up not ever touching two of the tiles. I would be very happy to be proven wrong though. Was the question about the expected time till all coins are facing the same direction?
A: In your "follow up" you add a very important condition: that the table is rotated "arbitrarily".  This word matters: if you said "randomly" we might try a randomized algorithm (just keep flipping coins until you're done, which you must be in the limit).  But "arbitrary" implies that perhaps it's not random and there is an adversary trying to cause you to fail.
This topic is central to the theory of algorithms and "worst-case analysis."  In any case, Ross's answer works, but he assumes that you will know when you're done (a condition you did not stipulate, but is required).
A variant of this puzzle: Suppose you have wine glasses instead of coins (you can feel their orientation and flip neither, one, or both each turn).  You must devise an algorithm which is deterministic and which the adversary knows ahead of time that is still guaranteed to work.
