Hi there, I'm part-owner/administrator of eMonsterhost.com which has been serving the industry since 2002. We have GD and PHP 4.0 on our servers. We have some very competitive plans as well. You can view them here if you'd like: http://www.emonsterhost.com/compare.htm Thanks and let me know if i can help
I'd say every single host has GD installed if they're running PHP4 unless they want to be out of business.