First, pick the camera you like. The only reason for taking the media into account is if you a preference because of another reason.
I won't mention them all but:
SM - SmartMedia: Small and light, but also not rugged. Ideal for very small items, like pocket MP3 players, where size is critical. Sizes tend to lag those available in CF (see below) and they come in 2 voltage types. I would not trcommend them except for small pocket cameras.
CF - Compactflash: Rugged case, sizes up to about 512Mb, but the affordable ones are the 128Mb (just got one in LA for $43 + tax). 512Mb is about $280.
CF/2 - Compactflash TypeII. Same principle as CF I but a bit thicker (5mm v 3.5mm). The advantage here is that you can get IBM Microdrives in the same format up to 1Gb. The 1Gb drives are about $340 drives. I picked up a 340Mb drive in Tottenham Court Road for about £110. They retail in the US for about $200. They pull more power than a solid state card however, is the only real advantage is the larger size allowing more high quality shots to be stored.
. .Sony Memory Stick: Sony proprietry, so you will not find anyone else using it. There are also different versions for video and audio, so you cannot swop them around. Not cheap.
My opinion? If it is a factor, go for one using CF II cards and, initially, use 128Mb cards. 512Mb ones will come down eventually.
Personnaly, I use a Microdrive so that I do not have to worry about space or carry extra cards around.