Podés hacerlo de dos maneras:
1) En el HTML poner el tamaño de la imagen que vos querés, con los atributos dentro del tag: <img width="x" height="y" ... >. Esto te va a funcionar, pero la calidad va a ser bastante pobre.
2) La otra, como vos decis, es usar algo que procese la imágen y la deje mas chica (usualmente casi sin perder calidad). Si estas usando HTML estático (es decir, ni ASP, ni PHP ni nada por el estilo del lado del server), lo único que te queda es usar algún applet de java que te haga el proceso, que se ejecutaría en el cliente. Esto quizá sería engorroso para el cliente, ya que tendria que esperar que se baje el applet, y alguna biblioteca de procesamiento de imágen a su browser, todo para ver una simple imágen.
Una tercera posibilidad es que generes dos páginas, una con una imágen mas chica (o thumbnail) y después otra con la imagen full, y pongas un link en la primera y si la persona le interesa clickea para ver la segunda.
Y tambien, el IE6 tiene resizing automático, es decir, te acomoda las imágenes que no entran al tamaño de la ventana del browser, pero eso lo pueden aprovechar, obviamente, solo aquellos que tienen IE6.
