¡Bingo! El EXPLAIN ANALYZE mostró un "Seq Scan" masivo en orders.
Creé el índice compuesto (user_id, created_at) como sugirió el segundo comentario y el tiempo de la consulta ha bajado a menos de 50 milisegundos. ¡Increíble la diferencia que puede hacer un buen índice!
Muchísimas gracias a los dos, me habéis salvado.