I have my limit set to 8meg, and it works fine. You can go quite a bit higher and it still works fine too.
But, since your host won't change it, you can use the FTP option that Gallery offers. Check out the installation Readme file for info on how to set up the folders to allow certain users to use FTP to send larger files.
Basically, you have to create a directory for each user that you want to have access to FTP uploads, then create an FTP Account for those users pointing to their respective directories. Your host will have to allow you to create additional FTP accounts for this option to work for you.
They FTP their files up, then they go to the Gallery Upload screen, where you can choose to process the files you have FTP'd. Then you'll be able to enter a title, description, and choose a category for each one.
Just a thought, does Gallery have a cron job, or any other check, to clean up the FTP folders at any time? I could see someone uploading lots of huge files, then never going to the Gallery to process them, and they'd be out there using up space...
Because of course, Gallery quotas are only enforced when they process the files. They can FTP up anything they want (depending on any FTP quotas you may set, of course).