A glass of water with ice-cubes in it. Where's the water the coldest; at the top or bottom?
Interesting question!

A few things first:


  As the ice melts, it cools the water around it.


Technically, the ice cube melts because the water cools down. This may sound ridiculous at first, but you must consider the fact that the ice melts because it has drawn "heat" (energy) from its surroundings. The "surroundings" being the air and water that surround it (but the water's more important since it's a better conductor of thermal energy).


  Given that cold water is denser than hot water, I would presume that the cold water would sink to the bottom...but it would warm as it sinks, reducing the density.


You're right, cold water is denser than hot water. It is helpful to note that it shouldn't be too cold though. As the temperature of water drops to 4 °C, the density of water gradually increases. However, as the temperature drops below 4 °C the density of water actually begins to decrease and water in this range easily "floats" over water in the room temperature range.




  Meanwhile, the ice is still melting and giving off its cold to the surrounding water.


Ice isn't giving off its "cold", rather, it takes in the water's "heat" (thermal energy).



Back to your question.

As Max mentions in his answer, you have done a particularly good job of indicating what physical parameters we're dealing with; the really important ones being the temperature of ice, temperature of water (at the time you put the ice in) and the quantity of ice used (at least with respect to the water).

But assuming you're drinking water (originally at room temperature) out of a 250 ml styrofoam or plastic cup, and you used two (normal-sized) ice cubes and that you began drinking the water a minute after you plonk in the ice cubes, the water should be colder at the top than at the bottom.

Consider minute, imaginary layers/regions/packets of water in the cup (thinking about this in terms of water "packets" rather than water molecules is easier to comprehend). Also, think of the cup as having three (crudely demarcated) regions: Top, middle, and bottom.

Packets of water immediately adjacent to the ice cubes are in thermal equilibrium with the outermost regions of the ice. However, these packets soon gain some thermal energy from other water packets that are adjacent to them. So as these packets slowly rise in temperature, from zero degrees to past 4 °C, they sink and new packets occupy locations adjacent to the ice. The cycle repeats for as long as the ice is there.

Now, as those packets of ice sink, they gain more thermal energy from the packets of water they come in contact with on their way down. This, coupled with the viscous effects of water results in the mild "warming up" of the sinking packets.

Now since they warm up a bit, they tend to rise back up. Back at the top, they're get cooled and sink again. This process repeats for as long as the ice remains in the water.

Take a step back, and you'll see that the middle of the cup ought to be cold, the bottom of the cup ought to be colder, and the top of the cup is the coldest.

So even if the ice cubes aren't actually touching your lips, you'll find sipping the water at the top to be colder than sucking out water from the bottom through a straw.