In Paris, there are cheap LCD displays in some bus stations that give you the time until the next bus arrives. I am assuming that these are just giving the hypothetical times, i.e. the amount of time until the next bus on the schedule. I'm proposing something similar and a little more sophisticated, but cheap--no GPS, no internet, no satellites.

Ok, so select bus stops have a solar powered RFID reader, and each bus has a RIFD tag. When the bus arrives or passes the stop, the reader logs the time. The times are then put through a Gaussian filter or something, and the stops would come to know the "true" bus arrival times. This may offer a slight improvement over the posted bus schedules, but in addition it would provide the MTA valuable traffic info. For the user, it is a lot like the paris system--there is a little display that says the amount of time until the next bus--except maybe more accurate. Also, if you run out to catch a bus and it has already come and gone, the display will be reset and you'll know that you've missed it.

Afterthought: Maybe RFID is too expensive. It could be done using cheap radio technology and PICs though. Like maybe some of those radios from sparkfun.