Talk to that separate company to see who holds the Domain Name records. It is perfectly fine for you to have email hosting with one provider, and your web services hosted with another.
Whoever it is that holds your records (this info is available in the public domain with DNS searching tools btw) can 'point' your currently inactive www records to a different hosting company.
You could build a web site first on a new server with your new hosting company, not 'tell' the world about it initially ... then 'point' the www record at it afterwards.
The new hosting company can tell you how to transfer over email. There are a variety of possible issues that could arise. Good luck =)