There is a fun generalization of the game. Assume the penny has (unknown) bias p. You want to output a new flip with bias some function f(p). So f(p)=1/2 is what you described, ie how to get a fair flip. For some functions it can be even easier, e.g. f(p)=p^2 - definitely only requires two flips.
How about:
f(p)=p^2/(p^2+(1-p)^2)
f(p)=2p(1-p)
f(p)=3p(1-p)
f(p)=sqrt(p)
The last two are tricky, I took them from a paper "functions arising from coin flipping" by Wastlund. (The quantum generalization is even more fun, but this text box is too small to contain it.)
How about:
f(p)=p^2/(p^2+(1-p)^2)
f(p)=2p(1-p)
f(p)=3p(1-p)
f(p)=sqrt(p)
The last two are tricky, I took them from a paper "functions arising from coin flipping" by Wastlund. (The quantum generalization is even more fun, but this text box is too small to contain it.)