You'll get a lot of different answers! After 50 years of picture-taking with everything from 35 mm to 8x10, I feel that what I am looking for in a 35 is GOOD auto-exposure, since I feel that if I have time to use a separate meter (in itself a good idea), I also have time to use a bigger camera. 35 mm cameras need to be fast, it's what they do best - technical quality can be more than acceptable with a 35, bigger cameras are always better.
The worst thing to avoid is an older camera with center-weighted metering (for example, Pentax M series). This type of metering gives good results only with average subjects, it's really hard even for an expert to figure out how to compensate for other types. Nikon for some reason seem to do better center-weighted metering than anyone else.
So-called matrix metering is astonishingly good, it will get the exposure right in 95 to 99% of cases, the only thing is that some makers' matrix metering is only semi-intelligent, it works great on horizontal shots, gets totally confused if you turn the camera round. I agree with others that auto-focus is dispensable unless of advanced specification (range restriction, choice of focus spots, etc.).
Others have mentioned various types of older Nikons, these are very good, I personally have a Nikon FM3a, it's got everything I like and handles like Nikons always have way back to the original F model of 1959.
Someone said "the camera body is only the carriage for your film". Absolutely disagree - a poorly made or worn-out SLR body will have a high vibration level that will wreck the sharpness of virtually every shot.
Whatever you buy, now is a great time to buy it, with staggering bargains in good second-hand equipment! Have fun!