Una muy conocida y fácil de usar es http://www.shrinkpictures.com/
Abrimos la página y bajamos hasta ver algo así: Pulsamos en "Browse" y se nos abrirá un diálogo para elegir el archivo con la foto que queremos reducir. Yo he elegido una foto enorme tal cual salió de mi cámara.
Una vez elegido el archivo marcamos el tamaño en píxels que queremos que tenga la dimensión más grande de la foto. Los tamaños predeterminados son 760, 600, 350 y 100 píxels. Para según qué fotos, 600 podría ser excesivo y 350 un poco pequeño, pero tenemos la opción de marcar la casilla "Custom" y escribir ahí el tamaño que queremos, por ejemplo 450.
También podemos reducir la imagen a un 75%, 50% o 25%, pero si no conocemos su tamaño original esto no nos sirve para hacernos una idea del tamaño que tendrá una vez reducida.
Se puede optar por pasar la foto a blanco y negro (greyscale) o a sepia, vosotros veréis

Después elegimos la calidad deseada, que puede ser good, better o best (buena, mejor, la mejor). A mayor calidad mayor tamaño de archivo pero la imagen no cambia de tamaño. Para la mayoría de los casos good es suficiente.
Pulsamos el botón "Resize" y esperamos un momento a que nos salga una pantalla asÍ: Nos informa de que la imagen ya ha sido reducida, hace publicidad de un par de sitios y nos dice:
La imagen original tenía 3872 píxels de ancho, la imagen reducida tiene los 450 píxels que deseábamos.Original Image Size 3872 W by 2592 H and 3169 K (3245117 bytes)
New Image Size 450 W by 301 H and 14 K (13973 bytes).
Pulsando en "Download this picture Now" nuestro sistema operativo abrirá un diálogo preguntándonos si queremos abrir el archivo, guardarlo, etc...
A partir de ahí es cosa vuestra. El archivo reducido quedó así: Hay programas especializados que lo hacen mejor, pero más fácil es imposible.
EDITO para añadir lo apuntado por Juantxo y Cecília:
Los usuarios de windows tienen también la opción de instalar el programa PIXresizer, que parece muy fácil de usar y hace lo mismo. Se puede descargar gratuitamente de aquí y su aspecto es este:

EDITO de nuevo para añadir un apunte de Vicent sobre cómo hacerlo con Paint en Windows:
- 1-En el archivo de la foto, botón derecho-Abrir con-Paint
2-Ya en el Paint, Menú Imagen-Expandir o contraer
3-Reduces el mismo porcentaje de Horizontal y Vertical (por ej poniendo 25 en cada casilla)
4-Aceptar, y si te gusta, Archivo-Guardar como y la guardas con otro nombre
La forma más sencilla de redimensionar una imagen sin instalar software adicional es utilizar Vista Previa, es una aplicación que viene por defecto con el sistema operativo:
- Abre Vista Previa
menu > archivo > abrir (busca tu foto)
menu > herramientas > ajustar tamaño
- Aparece un cuadro de diálogo. Como unidad escoge "píxeles". En el foro recomiendan que el lado ancho esté alrededor de 500px. Acepta y haz un "guardar como" para no sobreescribir tu imagen original