Either that or say you'll plot a massive boycott against them if they don't install GD. That should spark their interest.
Just kidding of course. My host, Vervehosting.com, has always been very gracious to my requests when I ask them to install some kind of PHP Library.. so I would try just asking first. I suppose it could depend how much money you are paying per month for your host, but I would suspect if it is $15 or greater they should comply with your request, if they want to get good feedback from their clients.
BTW: If any members have this installed and wouldn't mind if I add it to the first post under a section for demo's, please post your link in this thread, or PM me, so I can do so.