2
With GDlib you are limited to 8-bit colour (256 colours in total), so regardless of what gallery you use it is going to look crap for photos. All they need to do is enable GD2 and you'd be all set. If this is important for you, and they absolutely will not budge then I would recommend finding a new host.