There are alot of good cameras out there and I agree with your basic thought that a beginner should start out in 'manual'.

My first 35 was (and I still own it; shot it today in fact) an early 80's Minolta X-700. I think it gives you the best of both worlds. It's a manual camera, requiring you to set aperture and shutter speed. But it also permits Aperture Priority, or Shutter Priority, or full Program mode. It's a metal camera, and like the watch, it keeps on ticking...

I'm sure all of the major camera manufacturers have a similar camera somewhere in their repertoire. Its just a matter of finding the one the fits best in your hand and your budget.