Don't cancel the old host until the new one is up and running. (Yes, I know, but you wouldn't believe how many people do this. :-))
On the new server, have them set it up as something like "new.your_domain.com" or "www2.your_domain.com" so that you can wander around it and test without switching over the mail "www" until you're pretty confident everything works.
I don't know about Movable Type specifically, but if you have command-line access to the new server, you may be able to do something like this to import your entire database(s) from the old server to the new one:
mysqldump -p -u <your old Mysql Username> -h <your.old.Mysql.host> --all-databases ¦ mysql -p -u <your new Mysql Username> -h <your.new.Mysql.host>
(It should prompt you for your old Mysql password and your new Mysql password.) That should dump all the database and table creation data (as well as any data in those tables) from your.old.Mysql.host and read it into Mysql on your.new.Mysql.host.
If you only have one database, such as "myDb," then you'd do:
mysqldump -p -u <your old Mysql Username> -h <your.old.Mysql.host> myDb ¦ mysql -p -u <your new Mysql Username> -h <your.new.Mysql.host> myDb
(Note: WW translates the pipe into some other pipish character that is not really a pipe, so if you copy/paste that, replace ¦ with the thingy that looks like it. On my keyboard it's above the backslash.)
If you don't have command-line access to mysqldump and the mysql client, I'm not really sure what to do. :-) Does Movable Type have a database import/export thing built in?
I don't think it will hurt you in the search engines as long as the name and site structure stay the same, but I'm not 100% positive about that.