colonia has a few nice beaches actually, just that most visa-renewers don't head that way. When you come out of the port, head up the hill and you'll get to the main road...right takes you towards montevideo, left towards the old town. Go left but after a few blocks, look to take a right turn. That will take you towards the football stadium, continue along that road for a km or so and you'll find some "reasonable" stretches of sand, also with nice bars and shade at the back of the beach. It's not Antigua or Sardinia, but it's pretty OK for an afternoon's reading when the sun's out.
