If you can obtain a full backup of the database and codebase its not that painful but you do need to know how to change the user for database access both in the web.config file and in SQL.
If you don't have Ent Manager access to your database there are  third party modules that will do the db backup. 
What I would suggest is do a few test runs restoring the setup to your local machine and gettting it running there to get comfortable before doing the 'big' move.
If the site isn't that big and or only uses core modules try exporting the site and then reimporting it into a new setup to do this login as HOST or with a SuperUser Account got to Host|Portals and select the portal to be exported in the export templates section, then download the file, upload this to the new host and create a new site on the new host using this as a template. Try this procedure on a test machine first to see how it works as I have had mixed experiences using this method
Also whoever you choose to go with for your new host ask them if they can provide any help
HTH
Antony