I would recommend either a Micro Four Thirds camera, a Nikon 1, or a Canon S100.
Micro Four Thirds:
Under 1k - yes, depending on which camera you get; there are only 2 cameras that might exceed 1k when accounting for the cost of a lens: a GH2 and a E-M5. All others are well below 1k.
Smallish/easily portable - yes, with huge lens selection and ultra-portable "X" zoom series that fold into themselves for extra portability
Stupid easy to use/easy controls - you can use it on Auto or scene modes or whatever; has full manual controls too
Good AF - Excellent speed and accuracy, except for small, fast-moving objects (which you would need a Nikon 1 or DSLR for, but even the will miss a lot of shots, too).
Good image quality - MFT cameras with first generation (12MP) sensors are as good as Nikon 1, which is already pretty decent for prints up to, say, 16x20 at base ISO. MFT cameras with 2nd-generation sensors (16MP) can go even higher and are brushing up against crop-body DSLR image quality standards. The micro four thirds sensor area is 60% the size of crop body sensors (2/3 stop difference), but almost 10 times the sensor area of the smallest common compact cameras (over 3 stops difference). Despite the increase in megapixels, the dynamic range and high ISO performance improved for 2nd generation sensors, so I would avoid 12MP MFT cameras unless you really want to save a couple of hundred bucks. Yeah, you can find fire sales on things like the Olympus E-PL1 or Panasonic GF2 or GF3, but they are 12MP and don't come with an electronic viewfinder or articulating LCD, like the cheapest 16MP MFT camera, the G3. The G3 sells for around $550 including the capable base kit lens (equivalent to 28-84mm on 35mm film format). To be sure, though, even the older MFT cameras like the E-PL1 will easily beat something like the Canon S100 or other premium compacts.
decent zoom - kit zoom is decent, you also have a large selection for other focal lengths and apertures, including the ever-popular and small low-light lens, the Panasonic 20mm f/1.7. But that one's a fixed focal length lens. There are also superzooms like the Panasonic 14-140 but if you add that to a G3, it's getting up there in size and weight... still significantly smaller than a DSLR, but it's definitely not pocketable anymore. If you want a very compact zoom, the Panasonic X 14-42 for $400 retail price, is the smallest one made.
Nikon 1:
Under 1k - yes, but you pay a huge premium for its autofocus speed
Smallish/easily portable - yes, even the lenses are small-ish
Stupid easy to use/easy controls - you can use it on Auto if necessary; lacks full manual controls as of current firmware
Good AF - as good as DSLRs in medium to good light, though it falls off somewhat in low light. Responsive and fast. Can take lots of full-resolution photos per second, and even while recording HD video.
Good image quality - pretty good. About as good as first-generation micro four thirds cameras.
decent zoom - kit zoom has decent range; they also make a superzoom and telephoto lenses and a wideangle prime. But frankly lens selection isn't that great right now, and the lenses and bodies in Nikon 1 are no smaller than with micro four thirds.
Canon S100:
Under 1k - yes, even including LCD protector and spare generic battery and case, it'll be under $500
Smallish/easily portable - yes, and lens retracts too, no risk of losing lens cap
Stupid easy to use/easy controls - you can use it on Auto or scene modes or whatever; it's interface is kinda meant for those upgrading from P&S, and it even has helpful text descriptors in-camera; has full manual controls too
Good AF - this is the Achilles heel of the S100, or any premium compact, but if they don't plan on taking photos of moving objects or stuff in low light, and if they are okay with a bit of AF delay and the S100 should be fine.
good image quality - good by P&S standards, the S100 has a 1/1.7" sensor which is bigger than the typical 1/2.3" or even 1/2.5" sensors in cheaper P&S cameras; as long as they print at reasonable sizes (say, 11x14" or less), the quality of the shot at base ISO should be fine. If they shoot in lower light or zoomed in more often, then they will have problems staying at base ISO, though.
decent zoom - good zoom range covers mid-wideangle to moderate telephoto (35mm film equivalent would be 24-120mm f/2-5.9), but there is apparently lots of variation in lenses due to quality control issues that I am hopeful they've worked out; initially, some review sites had to get as many as 5 samples to get a lens that wasn't lopsided or something.
NOTE: If they don't care that much about video, they can save money and get the S95 instead. They lose a bit of resolution and video quality and zoom range, but otherwise it's basically a S100.