If you're on cPanel platform currently, there's no need to download files and then upload, simply create Full-Website Backup and transfer to the new server, then restore. This works if you've root access at new server, otherwise ask your hosting provider to do that for you (as this method is hassle-free and must be done free of charge).
When you're done with moving, you can change nameservers at your domain registrar to point to the new hosting server and usually there should not be any downtime.
404 must not appear if moving was done correctly and site is working fine on both old and new servers.
Changing a server for your site must not affect your SEO ranking, but please make sure the new server is fast enough, as crawlers do not like slow performance websites.
Finally, make sure you're satisfied with your new hosting provider and cancel current contract.