I'm not sure that rental bike was necessarily too big for you--maybe it was just because you hadn't ridden in a while that it felt awkward. The reason I say this is because I'm about your size and ride a 14" hybrid (the one in my avatar), and I remember it feeling a little weird at first since I hadn't ridden in quite a while either. Was it a women's bike, or was it a men's model (the proportions are different and that can affect how it fits you)? As for having to lean over before you could put your foot on the ground, that seems normal to me--you shouldn't be able to put your feet on the ground from the saddle if it's at the right height on most bikes.
2011 Surly LHT
1995 Trek 830