You're right: the parcels of water don't move purely perpendicularly to the wave's direction of travel, and so it's not right to call them transverse waves. I think teachers use water waves as examples in order to convey the idea of a transverse wave (if you don't get into the mathematics, the water sure looks like it's going up and down), rather than as an accurate description of the particle motions.

For other readers who haven't learned much about how water waves move, I've included the following figure:

As Jim mentioned, water parcels move in circles or ellipses, and so oscillate both horizontally and vertically. Note, in particular, the behavior when the water is very shallow: the water near the bottom moves horizontally back and forth in the direction of the wave's motion: near the bottom, shallow-water waves are longitudinal.

There is another way to define whether a wave is longitudinal or transverse: by the direction in which the restoring force acts. The restoring force is the force that is pushing the wave back toward equilibrium. This is a slightly better definition, because the (arguably) most important sort of transverse wave, the electromagnetic wave (i.e,, light) doesn't involve particle motion at all. One could say that the restoring force for water waves is gravity, which acts perpendicularly to the direction of wave travel, so water waves are transverse. (Of course, this ignores the fact that water waves are actually a balance between gravity and fluid pressure: pressure acts vertically and horizontally, and is what accelerates the water parcels horizontally.

Now I'll address the other inconsistencies you've brought up:

Wave speed should be independent of amplitude, but it isn't for water waves
A wave whose speed and shape are independent of amplitude is called a "linear" wave. (it can be described using a linear partial differential equation). Not all waves are linear, but most behave linearly as long as the wave amplitude is small. Water waves behave linearly (speed independent of wavelength) when their amplitude is much less than the water depth. When they reach the shore, this is no longer true, and their behavior becomes much more complicated. (Go to the beach and watch the breakers to see just how complicated. The patterns of traffic on a busy street also behave like a nonlinear wave system.

Wave speed should be independent of wavelength, but it isn't for water waves
Waves that have this property are called "non-dispersive" waves. This is because an isolated perturbation (a "hill" of water in the middle of a dead calm ocean) will travel without changing its shape. Not all waves are non-dispersive. Sound and light waves are non-dispersive, and so are shallow-water waves, but deep-water waves are dispersive. Their phase speed is given by the relation

  c = sqrt(g lambda / 2 pi)

So, in summary: water waves are not transverse, except in the sense that their restoring force is perpendicular the the direction of travel; they are only non-dispersive in shallow water, and they are linear except in very shallow water. Linearity, transversity, and non-dispersion are special simpler cases of waves in general; the fact that the real world isn't always simple is what makes science fun.

Oscillations on a string (or a Slinky (tm)) are the best examples I can think of of linear, non-dispersive, transverse waves.