Like most other answers, I agree that the solution is to create both time and distance enough for the person to notice you more gradually from farther away. My answer differs in the definition of the problem. The probable reason that many people are startled by you in the first place. I'll offer a simple way to avoid that, thus creating less need to use the often awkward or silly feeling solutions.
I believe the original poster made 2 errors in his assumptions.
One has already been addressed by other answers; "The starting point is the moment I stand behind them". Obviously you need to start sooner.
The second error is that you assumed you are "quite Ninja-like in my movements". It is not the stealthiness of your movement that startles people, it is how close you were able to get before they noticed.
Everyone has an arbitrarily sized bubble of personal space where they can feel comfortable until the bubble is intruded upon by another. The size of that bubble grows when a person feels they are alone. I suspect that your personal bubble is frequently smaller than those you interact with. You probably do not notice in social settings because the cues are smaller than being startled, and people try not to offend you in the case where you become a "close talker".
I experienced this just yesterday when a stranger engaged me in conversation. I was quite happy to talk to this person and remember thinking "I really like this person, I'd like to talk to him at length about his experiences." Then he took one step closer while continuing to talk. Then all I could think was "How can I end this and get away from this person?" He did not talk or smell offensively, he was just too close. The change in distance was less than the span of my fingers, yet the change in comfort level was dramatic.
A similar affect happens when you approach an unaware person, however they do not have time to suppress their flight reaction. This manifests as being startled.
You are not doing anything wrong. There is just an incompatibility in the personal space requirements with some people you interact with. I think that if you can routinely(always) attempt to maintain a slightly larger distance from some people, you will find first that they are less frequently startled, and second, they may be more willing to engage with you for longer periods of time.
Try this first with people that you have already startled, then try it with people that seem cold or distant. You may find they begin to warm up to you.
The great thing is, trying this does not require any awkward affectations like jingling your keys or clearing your throat. It has no negative side affects, the worst thing that could happen is it might not work for some people.
It can even work in cases you wouldn't expect such as those wearing headphones. Because if you maintain a larger distance, and approach from the front whenever possible, you are more likely to be in their field of view and much less likely be required to tap them on the shoulder. If you ever do need to tap someone on the shoulder to get their attention because other methods have already failed, never do it from directly behind. First try to get a full arms length away so they can't hit you in the face if they are startled. Then try to maneuver to their front or side.