The solution to this problem is to shoot at a slightly longer focal length, in other words zoom in a little. You don't need to use the wide angle to fit more into the frame, that's why you're shooting a panorama. The ideal focal length for stitched panorama shots is the equivalent of a 50mm standard lens, because this magnification most closely matches that of the unaided human eye. While digital SLRs and the Fuji S9600 have the equivalent focal length marked on the zoom control barrel, unfortunately most digital cameras don't tell you this very useful piece of information, so you're going to have to use a bit of guesswork. With most digital compacts that have a stepped zoom and a wide angle end equivalent to around 35mm, if you zoom out to the widest setting and then tap the zoom-in control twice, that should put you at around 50mm. It doesn't need to be exact anyway, just as long as it's enough to cure the perspective distortion.
The second major problem with stitched panoramas is exposure. In outdoor shots where the only source of light is the sun, the brightness of the scene will change depending on your angle to the sun, so as you turn the camera the exposure values will change. When you come to stitch your panorama shots together you'll find that the brightness changes between shots, most noticeably in the sky, resulting in dark bands in the finished shot.
The solution is to set the exposure manually. Digital SLRs and high-spec compacts have a manual exposure function which makes this easy. Simply take an exposure reading from a mid-point position on your panorama, and then manually set the exposure to this value. However with automatic compacts it is a bit harder. Fortunately most cameras will at least tell you the exposure information, displaying the shutter speed and aperture settings on the monitor when you half-press the shutter button. In order to match up the exposures between shots, take an exposure reading from at about the mid point of your proposed panorama and make a note of the exposure values. Next, position the camera for the first shot of the series, and again half-press the shutter and make a note of the readings. Most compacts only have a limited range of aperture (f-number) settings, so you'll probably find that the aperture will be the same as your first reading, but that the shutter speed will be different. The difference isn't likely to be much, probably no more than one stop, but even that is enough to show up on the finished panorama.