I was taught categorically that the velocity of a wave depends only on the medium in which it travels.
Now I just stumbled upon a sentence + formula that declares that "the velocity of sinus-waves that are travelling on the surface of deep water is dependent on their wavelength", followed by the formula $v=\sqrt\frac{λg}{2π}$, where velocity is dependent on wavelength.
I am confused: can someone help out by explaining the apparent contradiction?
You are talking about a different kind of wave, which is known as a gravity wave (not to be confused with gravitational waves that propagate through spacetime). Your first statement is true only for electromagnetic waves, as well as pressure waves or sound waves in air/water/in a solid. The nature and mechanisms behind these two kinds of waves are different. Thus, the same formula cannot apply to both.
I was taught categorically that the velocity of a wave depends only on the medium in which it travels.
I doubt that such a statement was made categorically. Relatively few statements can be made which apply categorically, in all circumstances. There are almost always limitations on and exceptions to the applicability of any statement in physics.
I think you must have misunderstood. Probably what you were told was that the velocity of a wave can be different in different media, but your teacher was not claiming that that was the only factor that can account for a change of velocity.
For example, the velocity of sound in any medium also depends on its density, likewise for the velocity of light. Density can change as a result of temperature or pressure. The dependence on temperature is quite easy to understand : hotter materials mean its molecules are moving faster, so the sound vibrations is transmitted faster from one molecule to the next.
Neither is wave velocity constant for all wavelengths or frequencies. You probably knew that because you are aware that light of different colours is refracted by different amounts, resulting from a refractive index which depends on wavelength, and refractive index is the ratio of light speed in a vacuum to that in the medium.
The technical term expressing the variation of wave velocity with wavelength (or frequency) is dispersion, and the formula you found is the dispersion relation for gravity waves on the surface of water. There is another dispersion relation for surface tension waves (aka capillary waves) on water (see eg Why do some types of waves disperse? and Why is the speed of oceanic waves not a constant like sound? ).
Wave velocity is usually independent of amplitude, provided the amplitude is small. However large amplitude waves such as high-intensity laser light can alter the refractive index of the material in which they are travelling thus changing the speed of light. The formula $v=\sqrt{\frac{T}{\mu}}$ for the velocity of transverse waves on a string is derived on the assumption that the amplitude is small so that tension $T$ is constant. Large amplitude oscillations increase tension which stretches the string, reducing its mass per unit length $\mu$, both of which increase wave velocity.
Even in the same medium and with the same wavelength sound or light waves can have different velocities depending on the direction in which they travel and their mode of vibration (longitudinal or transverse). For example longitudinal and transverse seismic waves travel at different speeds through the Earth after an earthquake, and the direction of polarization of light causes double-images in some materials like calcite.
So no, the velocity of a wave does not depend only on the medium. It can depend on many other factors.
The only relation which categorically does not change is the relation $$\text{wave speed = frequency x wavelength}$$ because this is a consequence of the definitions of these terms.
