No te voy a recomendar ninguno porque son cosas que van mucho en función de la experiencia personal.
Daboweb por ejemplo está en Interdominios, con un dedicado eso sí, y va estupendamente. Por ahí he leido bastantes buenas criticas de redcoruna aunque yo al menos no lo he probado. Yo lo tengo en dominioslowcost desde hace (creo) algo más de dos años y no me ha dado problemas, no te sabría decir como funciona el SAT porque no lo he tenido que usar nunca.
A ver, lo de las DNS es una pollada, simplemente tú tendrás un panel de gestión del dominio (no del alojamiento, aunque puede que los tengas en el mismo sitio) y ahí tienes que poner las DNS del servidor y cuando cambias de alojamiento tienes que cambiar ese dato; normalmente durante un par de días el sitio puede no funcionar correctamente porque la gente al ir a tu sitio sea redirigido a la IP antigua y no a la nueva y eso es todo. Desde mi experiencia nunca he tenido problemas con esto, las DNS se suelen propagar bastante rápido y mi sitio que yo recuerde nunca ha estado caido por la migración, en el peor de los casos no suelen ser más de 48 horas.
Lo que puedes hacer es mirar varias opciones y buscar info por internet, lo normal es que encuentres mucha gente a favor, mucha en contra, opiniones compradas y tal vez algo de pr0n ... luego es sopesar según lo que leas que opción sería la mejor.