We made on two trips good experiences with www.autoeurope.com
They have a location @ the airport in Fortaleza, and they were the cheapest (cheaper than Hertz, Avis etc.)
We rented a VW crossfox, which, while not a 4weeldrive, had a bit more clearance than a normal small car.
When we brought it back after 3 weeks on the beach, filled with 3'' of Sand inside, we needed to pay 10 bucks extra for cleaning, which I deemed fully adequate
PS: just make sure that you note even the smallest scratch or anything that could look like, might save your ass big time in case you really add some scratches