pluto459 -- if your 2000x2000 images won't resize on the server, and you want to use those for Zenphoto to resize automatically, then there's no getting around that memory limit... sorry. No gallery using the GD library will work on images that big on your server, it's just not going to happen.
It's like asking to fit ten gallons of water in a five gallon bucket... there's no way I can make the bucket fit ten gallons for you... you have to get a bigger bucket, or put less water in it. So since your host won't change the memory limit and make your bucket bigger, your only option is to use smaller images, or move hosts. Period.
Zenphoto is exactly what you need, you just need a better host with more memory... or ImageMagick support in Zen (offloads the processing outside the PHP process), which could be coming soon, but not that soon...