The older cars get, the more Hondas and Toyotas really do stand out. Unfortunately, this also makes them fairly expensive as used cars.
The "budget" compact I tend to recommend is the Ford Focus. The 2008-2011 has been pretty reliable, they handle very well, and used prices are much lower than for a Civic. Reliability for those 2007 and older is iffier. Not awful, but clearly not Honda territory.
A Chevrolet Cobalt might also be a decent bet. I wish we had more reliability data on these, so I could be more sure of their reliability. The data we do have is promising.
The Elantra also looks pretty good in our stats. I'm adding this in an edit, or I'd also list it to the right.
With any of these, newer will be better. Many cars start having more problems, if not necessarily major ones, after the first 6-7 years and the first 100,000 miles.
I can attest firsthand that Mazdas, at least those old enough to be within your budget, will rust.