In the world of P&S cameras (I'm assuming that you're not getting an SLR given your needs for video and your budget), don't restrict yourself to just canon and nikon. Yes- those 2 make some of the better pro glass, and if you were looking to spend $1000+ on a body and a little more for a lens, then I'd say those two are the way to go.
In the compact world companies such as Fuji, Panasonic, Kodak, and Olympus make some truly remarkable cameras. Check out the Fuji F30 (and the new 31). Those 2 cameras have image qualities that rival some of the Nikon SLRs. Lumix (panasonic) makes some pretty good stuff, though high noise is an issue with their CCDs. The main reason to go for them is the fact that they use Leica glass, which is head and shoulders above anything else anyone makes. Sony uses Zeiss lenses (not too shabby either), and some of their H models (H5 and H9 seem to be good as well). The sony cameras are likely to get you some of the better video quality for a still camera. Olympus has been making excellent optics for decades, and their new UZ 550 has a rediculous 18X zoom, which will allow you to use the camera for a number of different situations. Look around a bit on
DPReview, and see what the experts say.