All other machines/programs seemed to be independent entities (e.g. the Keymaker didn't revert to someone else when he died), but it looks like the Agents have to take over someone's body - if they could just appear, they would have, e.g., in the subway station in the first movie. Why do they not have bodies of their own?
This is not canonical, but in-Universe speculation.
Pretend that the humans - and agents are objects (programming wise).
It takes time and resources to create an object (the body), considering the complexity of the sim.
So, it's cheaper to super-impose the agent-specific constructor on top of already allocated and computed human body object, than to create one from scratch.
On a separate note, as per Morpheus, the agents are bound by the rules of their world. They are fast, but they can't teleport. Appearing an agent with no body to inhabit would be tantamount to being able to teleport.
Although Agents have a lot less "powers" than normal programs (like your Keymaker example) there are only two significant differences otherwise.
- They need a host body to exist (as described in your question).
- They return if you kill them.
The second point deserves explanation. When Neo did his weird jumping into Smith, Smith was supposed to be actually destroyed (yet refused to disappear and became a virus later on). This is not what I mean. I mean a normal lethal injury (like a gunshot). If you shoot an Agent, you don't kill the agent, you kill the host.
It is not too much speculation that this is heavily related to their requirement of host bodies to begin with. If they only control a human (including its appearance) it also explains why they are bound to the rules of the Matrix and cannot be killed. It's an extra layer of indirection if you like.
P.S.: Although the Agents and the "free humans" (in the pre-Neo era) had all reasons to believe that Agents were practically invincible by humans, the machines knew very well that at some point an Agent-killing One would emerge, around the time, the Agents would be required the most. This mean that robust, recyclable agents (note the lower-case) would be required. Also perhaps the Oracle figured that "free humans" would hesitate to kill the human host compared to a program, if at least to a very small amount.