The Domain used for your media does not matter, you can link to any media file.
We have a tool in PowerPress that makes updating/changing the media URLS a snap. Go to the PowerPress menu on the left and navigate to the "Tools" page. Click the option half way down the page to "Search and Replace Media URLs". This tool will first give you a preview of the media URLs you will change as well as verify the new URL exists.
depending on your media download traffic bandwidth needs, there's not too many services to pick from. I have herd good things about DreamHost, though they are not podcast specific. They provide you web hosting and leave it up to you to figure out how to name your media files, upload, etc...