And if so, how did he imagine that light moved at different speeds in different media?
Yes, Fermat believed that the speed of light was finite, initially in reaction to the muddle created by Descartes, who wanted to have it both ways, the speed being infinite, yet different in different media, see Nahin, When Least Is Best, p. 107:
"When Fermat read La Dioptrique he was unimpressed and, as mentioned earlier, was blunt in his criticism. He wrote, in part, “of all the infinite ways [to analyze the motion of light] the author [Descartes] has taken only that one which serves him for his conclusion; he has thereby accommodated his means to his end, and we know as little about the subject as we did before.”... Further, Fermat rejected as nonsense Descartes’ assertion of the infinite speed of light and his subsequent illogical argument that light travels faster (than infinity?) in water than in air. Fermat’s position was that light traveled at a (very fast) finite speed in air, and that it was slowed when traveling through a denser (“more resistive”) medium such as water."
But the order of causation was reversed. Fermat first decided that light traveled at finite speed, and only later came to the least time principle, when he learned that the Snell's law was experimentally confirmed:
"Fermat initially believed that, since Descartes’ derivation was clearly (to Fermat) built on sand, then the “ratio of sines is a constant” result must be incorrect. Eventually Fermat learned that the formula was, in fact, generally accepted as true because it could be verified by direct experiment! This greatly puzzled Fermat; how had Descartes managed to derive the correct law of refraction from erroneous arguments?... With Fermat’s subsequent great discovery of the “principle of least time” (discussed later in this chapter) his quest ended in 1658 with success... Fermat’s solution to finding a physically correct derivation of Snell’s law of refraction was the result of developing a generalization of Heron’s derivation of the reflection law."