VPS hosting from eapps.com is a reasonable compromise between cost and hosting service quality. I use it to host a
hudson CI server.
This entry explains how I set it up up to a point where I can build using maven a java project hosted on a ssh protected git repository (on github). I will not go into the hudson specific stuff, the hudson wiki is usually complete & well worded. But I will spend more time on the OS specific stuff such as daemon configuration, ssh specifics, etc...