Is it possible to reduce image filesize on the fly (when users enter my website)?

It is possible to re-size images on the fly if you are comfortable programming in PHP. Judging from your question, I expect that your not there yet. If that is the case, you should check out the Regenerate Thumbnails plugin. With this plugin, you can change the images sizes you want in the media settings page and then re-size your images all at once, in groups or one at a time.

If you are comfortable programing, you need to check out the WP_Image_Editor class. There are several tutorials on the web that will help you get started.

Update: You say you are comfortable coding so here it goes. You will need a function that will grab the image, adjust the quality and stream it to the browser. I do something similar in a plugin I am working on.

You will need to create a new slug (in my case it was http://my.domain.com/thumbnail). Each image you want to adjust the quality on will use the url http://my.domain.com/thumbnail?imageurl=myimage.jpg. in functions.php you need to hook it with add_action( 'parse_request', 'yourfunction' );. Then:

function yourfunction ( $wp ) {
    if ( 'thumbnail' == $wp->query_vars['pagename'] ){
        $imagefilename = $_REQUEST['url']; // change to real path left to you
        $image = wp_get_image_editor( $imagefilename );
        $image->set_quality( $jpg_comp_level );
        $image->stream();
    }
}

Hope this helps