He probado a iniciar el S4 en Modo Seguro (con el que sólo se pueden iniciar las apps del sistema) y sigue ocurriendo. Por lo que descarto que sea alguna app instalada...
La gracia es que hay momentos en que extrañamente tarda más tiempo en "reiniciarse" (me ha dado tiempo hasta a hacer screenshots del cajón de aplicaciones para saber el orden en el que las tenía colocadas y no tener que calentarme la cabeza si lo tengo que formatear finalmente).