I am a Nikon fan, but I use CoolPix 4500 (should switch to CP8800 or D70). Check out Canons (Ixus and Powershot series). Pentax has some nice models as well. Olympus' Mu cams are great, but Mu Mini is a bit expensive for you (it has the best screen when compared to the size of the camera I have personally seen).
I personally would go for a bit more expensive camera, since they are just superior in every aspect, and the bit higher cost is worth it. Better pictures, more options, yadda yadda. Remember: it's not just the allmight megapixel count that matters! You can have a 5 megapixel camera which takes far worse pictures than 4 megapixel camera, just due to worse optics.
Also, my very limited experience suggests that you'd get a camera with CompactFlash cards, because they are big in both physical and computeresquecal size.