Let me throw out another option that is very reasonably priced and has great flexibility: the Canon S30.
It's a great 3.3 MP camera that can be had online for $350. Canon makes a housing for it that can be had for $150 online. The camera can be used on automatic very easily, or has just about every manual feature you could want when you wish to expand your control. It's a GREAT snapshot camera since it slips into a shirt pocket very easily.
I've had cropped shots blown up to 8x10 that look great. I think full frame could go much larger. If you want more pixels, the S40 is identical and $100 more at 4MP.
I agree with others to avoid 1.3MP.
While $500 gets you no flash, I've gotten some good results without it. If you'd like to read a review I wrote on the camera, I wrote a gear review at the Rodale's site:
http://www.scubadiving.com/members/gearreviews.php?s=465
The review has some samples of UW shots and a link to some topside shots. Also, there is a link there for a great camera review site, IMAGING RESOURCE. It's a great place for you to do further research on any digicam.
Do not short change yourself on your camera. While you don't have to spend a fortune, don't cheap out. Imagine all those once in a lifetime shots (topside and below) that would be special if only they were sharper, or more resolution, or properly exposed.
You're better off, if limited budget, to NOT get a strobe, or even NOT get a housing, than to get a poor quality camera.
And BTW, as a new UW photog myself, I think it's best not to have a strobe for a while. Just adding the camera adds so much to think about and concentrate on. Better to get used to those added tasks first. Wait untill your first night dive: camera in one hand, flashlight in the other, BC hose in .........
GB