Has anyone ever timed instructoin execution on a basic stamp 1 module?  I
    dont see how they can get 2000 instructions per second when it takes at
    least 500us to reliably get one byte of data from a serial eeprom.

Why do you think it takes 500us to get one byte of data from the eeprom?
The way I read the 93c46 datasheet, you ought to be able to get an arbitrary
byte of data from the eeprom in about 20 clocks worth, at up to 2MHz - which
would be about 10 us.  I don't think firmware on a PIC can run the clock at
2MHz, but I'd be surprised if it took more than 200us...

Note that some EEPROMs have a more complex communications scheme that would
cause the reads to take more clock cycles (typically, they require extra
bits to address the chip as well as the data address within the chip.)

BillW