I hit the local flea markets on Sunday morning and 
  a very occasional yard sale if I see potential while 
  driving past.  I also hit Brimfield maybe once a 
  year.  I can attest to the scarceness of good benches 
  for sale, and I think I've got some of the better 
  flea markets around from the sounds of other list
  members.  I think Todd nailed it; he's a "professional" 
  hunter and I'm a weekend warrior.  There's a big 
  difference, and I've seen that difference first hand 
  when I've been able to sneak out of work and attend
  a week-day auction.
     
  Back to building benches.  I'd like to reiterate the 
  "just build something now to get going" approach.  I 
  took this approach and have not regretted it at all.  
  My top is cottonwood (eek!) with some stud-grade 2x6's 
  around the perimeter, and plywood "torsion boxes" 
  filled with concrete for the base.  It ain't that
  pretty, but it's sturdy and so far its lack of features 
  hasn't slowed me down.  The materials are what I had on 
  hand, not planned and purchased.
     
  If I had it to do again with purchased materials, and 
  this actually might be the approach I take for bench #2 
  (on the path to *the* bench), I would use a bunch of 
  2x6's and carriage bolts.  Base joinery would consist 
  of full width/thickness 2x6's serving as tenons, and 
  double 2x6's for legs with a 2x6 spacer to form the 
  mortises.  The top would be 2x6's pulled together with 
  a few threaded rods.  Probably a diagonal or two under 
  there to stiffen it all up too.  Tools required are a 
  saw, a brace, and a bit.  One weekend tops *IF* 
  (big IF) you want to put-up with the ridges on the top 
  formed by the chamfers on the corners of the 2x6's.
  If you mind those ridges (I would), then you have to 
  edge joint each 2x6.  That is more of a time investment. 
  The only way to then maintain the weekend time-line
  is to briefly go away from exclusively muscle power
  (don't worry, we'll all turn our heads for a few moments).
     
  I agree with those who say build your bench because I 
  did learn quite a bit building mine; not in terms of 
  woodworking but in what I wanted out of my bench.  I 
  don't think the first bench needs to be *the* bench 
  though, even though it will see service for a minimum 
  of 4-5 years longer than you expect. ;-)
     
  As an investment in the future, buy a nice vice to hang 
  on it.
     
  Kevin, in Southampton MA