I would search around the Offers forums and check with few hosts there that are already offering PHP5. Also try using the Host Quote option and see what you get.
█•CirtexHosting•Providing Affordable and Quality Web Hosting & Reseller Hosting since 2003 █•LINUX based cPANEL/WHM Shared and Reseller Web Hosting with Fantastico █•HostV VPS•Premium Virtual Private Servers & Dedicated Servers powered by cPanel/WHM █•We transfer your sites over quickly!•I eat penguins for breakfast ...
Most web hosts now offer both php4 + php5, and some have even started to offer php5 as default. Many changes for php can be made through .htaccess as Jedito explained above, or php.ini if the php is running as CGI for individual users.