I run a little web hosting business myself and from what I know about the industry most hosts should offer both at this point (with PHP5 as the default). If PHP4 is the default on your host, you can try adding this to an .htaccess file in the root directory of your site:
AddHandler application/x-httpd-php5 .php
If your host is running the latest version of CPanel, you should be able to access your control panel and change the default version yourself: Software Services -> PHP Configuration.
If that doesn't work, complain to your host and demand PHP5!
Most web hosts support PHP4 or PHP5? Any ideas on this one?