As mentioned in the question, the Doctor is an Emergency Medical Hologram:
The Emergency Medical Holographic program (EMH) was a sophisticated
hologram developed in the early 2370s by Starfleet and used on most
Federation starships in the late 24th century. It was designed to
provide short-term advanced assistance during emergencies in sickbay
to the extent of literally replacing a starship's medical officer.
He's meant for situations like in the first episode, and we see him staying calm, reacting about as fast as can be expected1, and knowing what to do for each injury.
1 His physical reactions have to be kept in the realm of believability for humans, since he would be expected to work alongside them in such situations. If he, say, walked/ran at twice the speed humans were capable of, he'd be getting in the way of normal humans that can't move that fast - he looks human, and in emergencies there's no room for uncertainty.
Here's a bit on what's been programmed into the EMH:
The EMH Mark I was first activated in 2371, and was programmed with 5
million possible treatments from the collective information of 2000
medical references and the experience of 47 individual medical
officers. The EMH was also supplemented with contingency programs and
adaptive programs to learn while serving as a supplement of a normal
medical staff in cases of emergency.
Dr. Zimmerman, proud at his achievement, decided to program the EMH
with both his physical and psychological likeness. The resulting
hologram was arrogant and irritable, and as a result was poorly
received by many Starfleet doctors.
On the "mental" front, his base programming is around applying and adapting what's already been programmed into him. Researching entirely new solutions to unexpected problems isn't something the EMH was supposed to ever be doing, that was the job of the ship's doctor. (And Zimmerman's own personality may have been unintentionally inhibiting him...)
The Doctor only started learning how to expand his programming at Kes's urging and Janeway's insistence that he acts as the primary doctor. Given that it's gone wrong at least once before, most likely he's just been given inefficient algorithms due to B'Elanna's inexperience in that particular type of research. (She's an engineer, not a doctor, after all..)
And as a final tidbit, computers in general are just bad at certain classes of problems. The complexity of something as simple sounding as the traveling salesman problem is unexpected to people unfamiliar with it. So something like open-ended research that requires waiting for physical responses when testing, means he has to exhaust as many possibilities as he can before choosing the solution he thinks is best before he tries it on a patient. I would guess that, most likely, the Doctor is thinking of and discarding an enormous number of possibilities before he comes up with a useable idea. This would mean it only looks like he's operating at human speed.