As long as you follow the procedure exactly the process will be completely seamless: subscribers won't even notice any difference unless they specifically check the feed URL.
Firstly, you need to move all the video files to the new hosting service, leaving the old ones in place: then you need to amend the feed so that the new URLs show in the 'enclosure' tags (these must be full URLs including the server name). Do not amend any 'guid' tags, even if they contain the old URLs.
Upload the feed, and check it by subscribing manually from the 'Advanced' menu. As long as it all works, you are ready to proceed.
In order to move iTunes to a new feed you need to add the following tag to the top section of the old feed, between the 'channel' tag and the first 'item' tag.
<itunes:new-feed-url>NEW URL FOR YOUR FEED</itunes:new-feed-url>
iTunes will normally pick this up quite quickly but you should leave it there for subscribers for at least 2 weeks - when they next check their iTunes application will transfer its attention to the new feed, and indeed this is the only way of retaining your subscribers. Be very careful when typing in the new URL because if you make an error and redirect iTunes to a non-existent URL you will not be able to retrieve the situation and your podcast will cease to function.
To check what iTunes is up to, click 'Subscribe Free' in the Store page for your podcast. Go to the Podcasts section in the sidebar: you should see your podcast listed in the main pane. Control-click (Mac) or right-click (Windows) the line for the entire podcast (not an episode) and choose 'Copy Podcast URL'. When you paste into a text program you will see which feed iTunes is working from.
Once iTunes has picked up the new feed - as I say this normally happens quite quickly, but that's not guaranteed - you can add new episodes exactly as you did before. Make sure you are updating the new feed, not the old one.