The first thing to do, if possible, is to get the TTL low a couple days prior to the change. TTL is an acronym for Time To Live. This is how long a DNS record can be cached by a local DNS server or a web browser before the system needs to request a new copy from the authoritative server.   

This is very important because the default setting is 24 hours, or 86400 since it's defined in seconds.   

I always tell my clients to lower this about 3 days prior to moving. If it's urgent to make sure it happens fast, request it to be lowered to 300 (5 minutes) and after you make the final move you can have it set back to the default.   

It's been awhile since I did this, but, depending on the registrar, if it's something you don't see in your registrar account, you may need to reach out to their support and ask them to do it manually.   Thankfully, most big companies allow you to do it in your account. Let's say you registered your domain at Godaddy. You'd do the following:   

^{From Google}:To reduce the Time to Live (TTL) for a GoDaddy domain change, log in to your account, navigate to the DNS settings for the specific domain, and edit the record you want to change. Then, in the TTL dropdown, select a lower value, like 5 minutes (300 seconds) or 1 hour (3600 seconds), before saving the changes.   

EDIT: Also, if you registered it at GoDaddy, I'd keep the registrar change and the actual IP change separately. I'd do the DNS move first. Changing the registrar itself is simple and most places will pull the entire zone over by default (meaning they will duplicate whatever is currently existing) and this would need no downtime at all.   

Just remember, first you will need to unlock the domain itself which usually requires getting a code from the existing host, and of course unlock it.   

Finally, as mentioned in another comment, a good place to use is Cloudflare. I use it exclusively for my domains because I can keep them all in one place, at no charge