Here is my take:
First, knowing a bit more would help. You said you really want a rebel. Do you want it for the control of a manual camera? For the creative abilities an SLR can get you? If so you may be ultimately dissapointed with any P&S (point and shoot).
The Canon S3 is a nice camera - 12X zoom makes it very versatile. It has auto ISO which is a very cool feature. It is a very new camera, so will have more features and what-not. The lens is reasonably fast, but not great. It's strength is 12x zoom and IS. This is the only camera of the three that cannot take an external flash. This camera can take AA batteries.
http://www.dpreview.com/reviews/specs/Canon/canon_s3is.asp
The Canon Pro-1 is raved about by those who own it. It is sold as haveing an "L" lens, but many complain that it's not really an "L". This camera is old - released in 2/04 and does not have the speed of the newer cameras. The big deal for me with this camera is that a) it has a much better lens and b) it can shoot RAW. c) It uses compact flash. For me these are big deals. For you they may not be. This camera takes proprietary batteries.
http://www.dpreview.com/reviews/canonpro1/
The Fuji is a nice little camera. Keys for me are it shoots ISO 1600 (Auto too), Shoots RAW, takes compact flash (And XD), and can take AA batteries. It can shoot in 3:2 mode which I like and is 9mp. It has the strongest flash of the three listed.
This camera has a smaller screen if that matters to you.
http://www.dpreview.com/reviews/fujifilms9000/
Compare all three:
http://tinyurl.com/ptsw2
Between the three, I'd probably pick the Fuji. Honestly though I personally would probably not buy any of them because of the EVF viewfinders. That annoys me to no end. If you don't know, EVF is an "Electronic View Finder" and means it's like a camcorder - the view in the viewfinder is a tiny LCD screen, not the real scene. Most will argue that you'll be using the LCD on the back of the camera to compose, but for me having a "pro-sumer" level of camera means I want a real viewfinder.
If you want quality photos and want to learn more about photography (or if you already know), then a rebel would be a better choice. As for lenses being expensive, there are quite a few less-expensive lenses which can produce fabulous results. The $200 35mm f/2 is a perfect example - it is capable of creating images you could never make with any of these cameras. The $340 Canon 85mm f/1.8 is another example.
Also don't forget that Sigma makes some wonderful lenses and a fraction the cost of the Canon counterparts.
Sorry if I muddied the waters...
All of that being said, of your listed choices I'd go for the Fuji.
GAD