Well, after testing driving several new and couple year old versions of a Prius, Smart Car, Yaris, Accent, xB, Rio, etc. and looking at a bunch of others including the Fit, Aveo, Focus, etc. (I lost count), I think it's going to be a Hyundai Elantra. Sacrificed a bit on fuel efficiency and my size wish, but the ride was better than others (except possibly the Prius) and after driving around a rented newish Corolla to look, that aspect grew in importance. Didn't get new down to $10K, but wasn't that far off. Was sure tempted by the used Prius' though (primarily for other reasons than it's known for), and even the Smart Car Passion (though easily the strangest ride of the bunch). In the end, as mentioned above, that warranty was a big draw.
Thanks for your comments everyone. They really did come in handy.