So recently we were taught in school that tides are formed because the moon 'cancels out' some of the earth's gravity, and so the water rises because of the weaker force. But if water is not compressible, surely any difference in Gravity shouldn't make the water rise?
incompressible: not able to be compressed.
compressible: In thermodynamics and fluid mechanics, compressibility is a measure of the relative volume change of a fluid or solid as a response to a pressure (or mean stress) change.
So water does not change its volume. The same volume of water can take many shapes.
When no other gravitational force except the earth's $1/r$ potential acts on the oceans, the equipotential surface is defined by the single potential, and the oceans settle in the shape of the equipotential. Because the earth is not really a sphere, these equipotential surfaces vary, but the idea is the same.
When an opposing $1/r$ potential, as the moon potential, is strong enough at time $t$ to add a $-1/r'$ ($r$ from center of the earth, $r'$ from center of moon) potential, then the equipotential form into which the water will settle is disturbed at that time of closest approach.
This is what the solution of the problem gives:
Figure 2: The Moon's gravity differential field at the surface of the Earth is known (along with another and weaker differential effect due to the Sun) as the Tide Generating Force. This is the primary mechanism driving tidal action, explaining two tidal equipotential bulges, and accounting for two high tides per day. In this figure, the Earth is the central blue circle while the Moon is far off to the right. The outward direction of the arrows on the right and left indicates that where the Moon is overhead (or at the nadir) its perturbing force opposes that between the earth and ocean.
So it is the ability of water to change shapes that generates bulges, and the motion of the moon that changes in time moves these bulges with respect to the earth.
Please note that there exists also earth tides, i.e. the ground also bulges as far as the elasticity of the solids it is composed of allows it. Also note that water tides can appear differently in different locations due to the geology of the ocean bottom and the land boundaries, and just because water is a fluid and obeys equations of fluid flow.
I think you have started from a picture of the tides making water go up and down that is a natural picture to have, but it is wrong: they don't. If that picture were right, you ought to be able to measure the tides just by digging a deep well.
What happens is that the influence of the moon (and sun) changes the shape of what is meant by "level" - technically, the equipotential surface, the surface where the gravitational potential energy is equal across the planet. Anna V's picture is the one to look at here.
Locally, this change in global shape translates into a tilt. A piece of sea or lake which was level a few hours ago now feels that it is not level any more, because the equipotential surface has moved on (following the moon). So its water does what any water does in those circumstances, which is flow sideways from "high" to "low" until it is level under the new definition. And water doesn't have to be compressible to flow sideways.
A good model of this is to take a big flat shallow tray and half fill it with water. Then tilt it from side to side. The surface of the water will end up horizontal (because that is the equipotential surface in your experiment), but it will do it not by stretching up and down but by sloshing from one side to the other. (The difference here is that the tray is moving relative to the equipotential surface, rather than the equipotential surface moving relative to the Earth, but the effect is the same).
The sloshing of the water in the tray as you move it is also important for tides. The difference in height between high tide and low tide in a perfectly frictionless perfectly inertialess ocean is only 18 inches or so. The fact that we get far huger tides in real life is down to the sloshing of real water in sea beds, and round coastlines of interesting shapes.
Tides are the resultant of attraction from earth (major effect), moon (secondary) and sun. Other planets'influence can be neglected. The position of the moon (and of the sun) cause a slight variation in equipotential surfaces on the earth, and the water as a liquid naturally tends to follow an equipotential surface. Of course those variations are by themselves far from moving the equipotential surface by meters! But here comes the resonance phenomenon: water is pulled to the west, then to the east and it behaves like a ball in a bowl: when you apply small forces to the ball but in the appropriate direction when it moves, you will see it go higher and higher at every step, until friction equilibrates all.
That's exactly what happens with oceanic tides, and this is the reason why you can only observe it in large oceans and not in closed small seas.
Lots of these answers expect you to know a lot about the way gravity works. From these, I've managed to come to the answer, and in this post I'll try to dumb it down to my level.
To start with, I'd like you to imagine a tray, or an empty biscuit tin - something with a flat base and rims. Now imagine you pour water into this tray (feel free to actually pour water into an empty biscuit tin if you like - just remember, nobody likes soggy biscuits)
Now if you leave this tray on a level surface, like a table, the water stays still(ish). What's keeping the water there? Ok, so you know it's gravity. Very easy, gravity is pulling everything toward the centre of the earth.
Have you ever seen the analogy for gravity, where you stretch out a sheet and put a large ball in the middle? The idea is, you can see how satellites orbit the earth by rolling pingpong balls around the sheet. It isn't perfect - you have to imagine everything is 2D, like you're looking at it from above.
Let's imagine that our sheet is made of plastic, and along with the ball, we pour some water in. The water pools in the middle, attracted to our ball - and is left to settle. Just like our tray full of water, the water attempts to move to the middle point of our ball, and rests when it reaches a surface it cannot penetrate.
Now, as we roll pingpong balls around, the shape of the plastic changes - and as the pingpong balls make their own tiny dents in the plastic, the water isn't quite as attracted to the ball. It still sticks close to the big ball, but as the little balls get closer, some of the water shifts slightly.
Note here what isn't happening: The volume of water is not changing at any point. Water is simply moving from one part of the sheet to another. Just like if I tip my tray slightly, the water at one side of the tray will be thicker, and the water at the other side will be thinner. The thin side is not more dense; my tray just isn't level.
Earlier I asked what was holding the water to the bottom of the tray. Let's try a slightly less obvious question: How do you know that your table is level?
How do we define "level"? You see, we go through life confusing causes and effects. For example, we think objects "have a colour", when in reality they simply absorb other-coloured light. We observe that an object "is moving fast", when in reality the earth is spinning through a rapidly expanding universe, any speed we assign to an object is minuscule in comparison.
When we say "This table is level", we are saying that the surface is perpendicular to the pull of gravity - i.e. if gravity is pulling down, then the table is stretching across at right angles to the pull of gravity. Yet this assumes that the pull of gravity is exactly the same at every point along the table. If we had some gravitational source above one end of a long table, then the table would no longer be "level" - at least, not according to our spirit level.
So I propose that the answer to your question lies in a fundamental mis-assumption: If the surface of a still pool of water is "level", it is because there is insufficient difference in the gravity from one end to the other. Waves are caused by the moon changing the very definition of a level surface, and the water is simply trying to catch up.