Why do tsunami waves begin with the water flowing away from shore? A sign of a tsunami is that the water rushes away from the shore, then comes back to higher levels. It seems that waves should be both + and - polarized and that some tsunamis should go in the opposite direction. That is the first indication of them would be that the water begins rising. However, other than situations very close to the source, it seems that the wave always begins with the water drawing away from the coast.
For example, the wikipedia article on tsunamis states that:  

In the 2004 Indian Ocean tsunami
  drawback was not reported on the
  African coast or any other eastern
  coasts it reached. This was because
  the wave moved downwards on the
  eastern side of the fault line and
  upwards on the western side. The
  western pulse hit coastal Africa and
  other western areas.

The above is widely repeated. However, when you search the scientific literature, you find that this is not the case:
Proc. IASPEI General Assembly 2009, Cape Town, South Africa., Hermann M. Fritza, Jose C. Borrerob, "Somalia Field Survey after the December 2004 Indian Ocean Tsunami":

The Italian-speaking vice council,
  Mahad X. Said, standing at the
  waterfront outside the mosque upon the
  arrival of the tsunami (Figure 10a),
  gave a very detailed description of
  the initial wave sequence. At first, a
  100-m drawback was noticed, followed
  by a first wave flooding the beach.
  Next, the water withdrew again by 900
  m before the second wave partially
  flooded the town. Finally, the water
  withdrew again by 1,300 m offshore
  before the third and most powerful
  wave washed through the town. These
  drawbacks correspond to 0.5-m, 4-m,
  and 6-m depths. The detailed
  eyewitness account of the numerous
  drawbacks is founded on the locations
  of the offshore pillars.

So is there a physical reason why tsunamis, perhaps over longer distances, tend to be oriented so that the first effect is a withdrawal of the water?
 A: I will simplify the question. When large waves come towards the beach there is always an undertow. Has an "overtow" been seen before the undertow?
My explanation while watching waves was that the waves break gathering mass on an incline. Growing in height they draw water symmetrically, but there is less water ahead, because of the incline,  than behind, and the water is sucked up by the wave crest before it arrives. I expect the same mechanism to hold for the much longer wavelength tsunami wave.
I guess data from high rocky shores might be enlightening. When I visited Japan I went on tour up the east coast from Tokyo and was impressed that there were no beach facilities and the beaches looked like garbage dumps. I was told this was because of the tsunamis.Long beaches ending up in  precipices of land overlooking them.
A: The positive or negative elevation of the leading wave is related to what happened to the ocean floor during the earthquake. If the seabed was raised, a crest should lead the tsunami; if it was lowered then a trough leads.
In the 2004 Sumatra tsunami, a piece of seabed of about 1000 km x 100 km went down a few meters. Another strip, located to the west of the first and with roughly the same size, went up. Because of this, the wave moving east (towards Thailand) was led by a trough. The one moving west, which reached Sri Lanka, India and Africa, was led by a crest. 
This is seen in the simulation of that tsunami shown below (by Kenji Satake, of the Active Fault Research Center in Tsukuba, Japan). In the red areas the water surface is higher than normal, and in the blue ones it is lower.

A similar animation, with some data added, is at 
http://es.ucsc.edu/~ward/indo.mov
A: Water waves are rather complicated, and the differential equations which describe them are call Boussenesq equations.  A tsunami is not a transverse wave.  It is a pressure wave with a longitudinal mode.  It also travels very fast at about 700km/hr.  What happens is that this travels as a pressure wave in the open ocean, but when it reaches a continental shelf the wave is reflected partially upwards.  This has the effect of converting it into a transverse wave as water moving along is now pushed upwards.  This is a very nonlinear process and nontrivial to model.  This pushing up of the water does initially cause water at the shore to recede outwards.  The wave which seconds later reaches shore is much more slow moving, and a lot of that wave energy is converted into the towering wave front that sweeps in.
A: Dear Carl, the recession of the sea level is an inevitable consequence of the mass conservation: the extra water in the tsunami has to come from somewhere. It comes from both sides - from the region in front of the wave as well as behind the wave.
So if the sea level is most elevated somewhere, it must obviously be lowered at both sides, too.
Imagine that you have a wave packet given by the function
$$ f(x) = \exp(-ax^2) \cos (kx) $$
The maximum absolute value of  $f(x)$ is at $x=0$, right? That's the tsunami. However, it's inevitable that the second highest absolute value which can still be seen is at the pair of the nearby local minima. The two maxima at even higher values of $|x|$ are already pretty much negligible.
A: Sitting in a pub with my pals, who all absurdly claimed that a tsunami wave "sucks" water from the shoreline, I once gave the following demonstration: I passed a ruler, on its edge, under a large table napkin, raising the fabric in a wave. As the ruler approached the edge of the napkin (the shoreline), the shoreline receded. This demonstration is not literally correct, of course, because it implies "suction", but i believe it is helpful in imagining water receding (through gravity) down the outward/seaward gradient.
A: It is a matter of conservation of mass. In order to raise the water a certain height, the extra mass of the water has to come from somewhere. That somewhere is the area directly ahead of the wave. So in the end the average height of the water does not change. Lower the level by 1 meter for 10 meters, and you have enough to make 10 meter wave with 1 meter width.
clarification:
  This effect travels at the speed of sound underwater, whereas the surface waves travel at a lesser speed, thus the dip precedes the rise.
A: Waters recede before tsunami waves rush towards the land because of fault dipping or fault collapse (faults collapse due to underground system disturbances like oil extraction).
Fault dip is characterized by downward movement of one fault wall resulting to its displacement. As faults gets displaced waters around the vicinity of the subsided fault will replace the space that the fault had vacated. Most of The waters that rush and overlap towards the land are from the oceans.
