In Lisbon I usually rent from small agencies through consolidators through economycarrentals. So far have not had a bad experience with the small agencies. Be sure to familiarize yourself with the toll system and take the toll tag option when offered by the rental agency as it's worth the hassle.

You should have the IDP, though it's YMMV in case of a traffic stop.