Does the body really make that big of a difference? I found a Fuji film body on Craigslist for $140 but didn't know if that would be a crap shoot. Putting a expensive lens on a shoddy body may not work well, but saving the money if it will would be nice.
It does make a difference. First and foremost, the body and the lens have to work together. For example, both Nikon and Fuji (S2 or S3) bodies use Nikon F-mount lenses. Canon EF lenses won't work or vice versa. Nikon has the widest array of lenses available.
Beyond that there are considerations such as:
Battery - the Fuji S2 uses 2 types of batteries (AA and CR123) this is a pain, but both are fairly common meaning you can still shoot even if you don't have a charger. The S3 did away with the CR123 and uses AA only - much better. I think most Canon models use some sort of rechargeable battery but not AA form factor, so you are not going to get one at the supermarket if you can’t recharge (buy a spare).
Shots per charge – my S2 may only give a few hundred shots per charge with rechargeable AA batteries. Many of the Nikons with their rechargeable batteries may get a thousand shots or more.
Sensor - most CCDs are smaller than a piece of 35mm film. This is called DX format. It's OK to use film lenses on DX format cameras but not vice versa. A film lens on a DX camera has an effective focal length of 1.5X whatever the lens is. i.e. a 50mm film lens on a DX camera is 75mm. If you have a camera with a full frame sensor, you must use lenses for film cameras. Full frame CCD cameras such as a Nikon D700 or a Canon 5D will be more expensive.
Size – a Fuji S2 or S3 is a BIG camera – one of the reasons they can use AA batteries. Nikon makes many cameras that use the same lenses but are much smaller.
LCD display – while it doesn’t directly impact the picture quality, it is really nice to have a large display on the camera to see your pictures. It’s pretty small on a Fuji S2 for example and this makes it hard to tell if you got a good shot or if it is a little blurry.
There are many others: megapixels, image size, sensitivity (ISO range), shutter speed range, flash compatibility, shooting speed, etc.
I’d check out some reviews of whatever cameras you are considering. A good place to start is
http://www.kenrockwell.com/