Changing Hosts - Huge Gallery Needing Moved

Hello,

My current web host is Ipower and I am looking to change hosts. Before I do, I wanted to get some information on moving the gallery. But I have a couple of problems/concerns:

1. The old gallery I currently have on my site was "integrated" with the original hosting package I bought. I clicked on "install app" and the Gallery was automatically installed. Afterwards I simply clicked and added images, etc. Over the years, we've added over 43,000 images. Since the new host most likely does not have this kind of one-click application, and since I am unfamiliar with php, where can I find instructions on installing the gallery when I change hosts?

2. My current gallery version is 1.3.4 Yes, very old! Will it even be possible to move the pictures I currently have to the new host when I install Gallery, and a newer version, on there? Here's the link if needed: http://okunenanime.com/v-web/gallery/albums.php

3. When I backup the gallery images, will I need to backup just the main images or even the thumbnails, etc?

Any tips or suggestion will be greatly appreciated! Perhaps even a step by step guide somewhere that I am missing? Due to horrible downtime with the old host and tons of internal server errors, I have made the decision to change, and quickly because I am losing "customers" fast! I am considering BlueHost, as it was recommended. If anyone knows of a host that's better and perhaps easier to complete this switching over process please let me know.

I also hope I made sense. The gallery is the heart of my website and it is crucial I transfer and upgrade it!

Thanks again for taking the time to read this.