For a lightweight, ultracompact stroller, we like our Mia Moda Cielo. It folds up very, very small and has an easy carry bag. It's also light (13-14 lbs, I think), has a well-designed bag, is padded, and does pretty well even on bumpy cobblestones.

Here's a picture:

http://www.miamodainc.com/strollers/cielo.asp

And a folding demo:

http://www.miamodainc.com/strollers/...demo_cielo.asp

You can get it on eBay for $120-130 with shipping.

Cheers!