Generally speaking when shopping for a point and shoot you want to look for the following:
- Largest possible aperture over the zoom range
- Zoom range to fit your needs(be wary of huge superzooms and their compromises)
- Size that fits your needs(smaller is convenient to carry but consider usability as well)
- Largest possible sensor
- Batteries that fit your style of shooting(Li-Ion for most, AA for some)
- Scene modes to help novice users
- Big high resolution screens
- Buttons that you are comfortable using(size and quality)
- Menu system that is intuitive and user friendly
- Resolution (higher can be better,measured in megapixels)
- Video capabilities
- GPS and or Wi-Fi
- Image Stabilization
- Larger ISO ranges
- Manual shooting modes such as Shutter Priority, Aperture Priority, Manual Mode
- Largest possible shutter speed range including bulb.
If you are really starting out fresh and want to keep it as simple as possible, make sure that the camera has scene modes that are easily accessible. A mode for "sports" for example is a great way to take images at a kids football game. Another thing to look for is a larger screen, but not so large that the camera is missing most of it's buttons. Some cameras now are featuring huge screens across the back of the camera but leave out essentially all buttons. Physical buttons can be very nice to have and screens(especially touch screens on current cameras) can be tricky for beginners.
One of the most common issues that people have with family photography and portrait photography is that they shoot in very low light indoor situations. To combat this I would recommend looking for a very wide aperture(allows light into the camera). An example of a wide aperture would be f/2-f/3 or a similarly wide aperture(small number). Another thing that can help out a great deal is having a wider angle lens, allowing you to capture the full scene even in a small indoor venue. Something the 24mm wide range is what I would recommend if possible, 28mm is quite standard as well but I wouldn't go beyond 28mm.
Travel photography really can include just about anything, and it means different things for different people especially depending on your destination. Generally speaking for travel photography you would want a wide focal length range. You want to have a nice wide angle lens as well as a telephoto lens. I would look for something from about 28mm-300mm if possible. Many people like to have a smaller camera for travel though, so you will want to weigh your desire for a long telephoto zoom lens with the size that you are comfortable carrying with you all day while you travel.
When searching for an ultra portable/compact point and shoot camera, keep in mind that you are likely sacrificing biggest in the area of the lens. It used to be the case that you might get no optical zoom at all with a very small camera. Now it is very common to still get a very respectable 3x optical zoom, such as a 28-100mm zoom or similar. Other things to keep in mind are the ergonomics. Many times very small cameras forgo grips or anything to hold the camera easily, so make sure to keep this in mind before purchasing.
With wildlife it is safe to say that you can never get close enough or have enough zoom. Look for very large optical zoom ranges, with image stabilization if possible. You also will want to consider what the aperture is at all of the zoom range, not just the wide angle of the range. For example, the Canon Powershot SD50 has a massive 24-1200mm (50X) focal length lens. At the wide end this lens has a maximum aperture of f/3.4, but at the telephoto end the maximum aperture is f/6.5. This is actually an astonishing lens, but just keep in mind that the maximum aperture can be variable and the telephoto end maximum aperture can be very important for wildlife photography.
You want to look for the depth measurement(how far can you swim down), usually in the 30ft range or so. Also the height at which are drop rated, usually around 5ft. For the most part waterproof cameras are somewhat limiting. The optical zoom can be limited to about 5x on these units. They typically have fair image quality but not quite as good as cameras that don't work underwater. One other thing to consider is the ergonomics. The buttons should be big and easy to use, as using them underwater can be a great deal more challenging.
Image quality should be important for every use case, but if it is the most important item on your list, what you should look for changes just a bit. Push towards the largest sensor size possible. A 1/2.3" size is common, a 1/1.7" size is a bit less common, but preferred for image quality if all other things are equal. High ISO performance is a metric that can be more complicated to understand, as you likely will have to look at online reviews comparing the performance the camera against others at similar ISO values.
If you want to focus on sports photography, many of the same tips that are outlined above for wildlife apply(big zoom range and large aperture). The differentiating point is that you will certainly want something that can shoot many frames per second(FPS). Something above about 4fps is great for sports photography, allowing you to capture multiple shots before a baseball batter can even swing through a pitch for example.
Of course endless special use cases exist. Do you need any of the following? Viewfinder, special zoom requirement, brand preference, external flash requirement, etc.
This specific case asked in the original question:
The specific models you point out you can take any of my above tips and easily compare on many websites. For example the Fuji FinePix F800 EXR that you mentioned has an aperture range of f/3.5 - f/5.3 and the Nikon CoolPix P5100 has an aperture range of f/3.0 - f/5.9. So the Nikon wins in the maximum aperture category since it has the wider f/3.0 capability(technically it varies over the range so this is debatable, but the maximum is better irrespective of focal length).