Your question is tricky to answer because it depends what you've got and what type of photo you're after.
In general there are 3 aspects that will affect image sharpness (excluding native camera+lens sharpness).
1) Camera shake; affected by the holding of the camera and by the focal length. The longer the focal length the faster your shutter speed has to be. A rough rule of thumb is 1/focal length=minimum shutter speed for a sharp shot hand held. That assumes a good level of fitness for the lens and a good posture.
For a 500mm lens that means you're up to 1/500sec minimum and for big lenses like that most people often need a bit more.
2) Subject motion blur; movement of the subject is the other area and here you've got rough limits. 1/500sec is really your slowest rough limit; any slower and you're introducing more and more chance for the motions of the subject causing blur. Of course that's just a rule of thumb;
If your panning a shot you might be able to use a slower shutter sped
If the subject is asleep or at rest you might get away slower
If the subject is running/sprinting or performing other fast actions you might well need a lot more.
3) Haze from air. Not really an issue most of the time until you're using something around 1000mm in focal length (so a big lens plus teleconverter). However sometimes strong heat can cause haze to be more apparent and more problematic in some situations. Thick fog or other particles can also have a similar effect.
As for a rule of thumb for focal length - 100mm longer than whatever you have at present

. Longer is generally better most of the time which is why wildlife is often a very expensive area of photography. 300mm is where it starts, but many really start at around 400mm. Anything greater is worth considering if you can afford it; but also have a mind that some lenses can take teleconveters. A 300mm f2.8 with a 2*TC is now a 600mm f5.6 lens for a lot less than a 600mm lens and lighter too. Sure you've lost some image quality but you'll still get usable images if you stop down a bit from wide open.
Another key point is to consider your ISO. An oft quoted mantra is "Keep the ISO as low as possible" and whilst this is true; its bad advice in general. With wildlife you've got to have that shutter speed fast - so often as not unless you're in blazing sunlight (which introduces its own problems) you'll be wanting to have ISO 400 or even 800 as your starting point for ISO. Only lowering it if you're getting fast shutter speeds and can afford to drop them a little.