I canβt remember the last time I saw a lamp hosting provider without GD. The imagemagick extension is not so widespread. if they start their server on their own, they really should be able to activate one of them, or both. in your place I would build full functionality with GD and (possibly reduced) imagemagick border. if they have not received a single one, show them the basic concepts of wheel and / or fire, they should be thankful.
PS: I came across providers who deactivated certain GD functions (which complicate calculations in a shared hosting environment), such as imagerotate and imagefilter.
stefs source share