For $500 there are plenty of good choices. First you should look into the different designs available: SLR, TLR, folder, rangefinder, press camera, etc... See if you can see how they might or might not work with your style.
I think the best deal for the money is with the TLRs. Minolta, Mamiya, and Yashica all make great TLRs that can be had for under $250. Rolleiflexes are more expensive ($350+), but they are fantastic cameras. My Rolleiflex is my favorite all around camera. It combines fantastic image quality with easy portability.
These days there are a lot of good SLR systems going cheap. The Norita 66 is like a big, basic 35mm SLR. They were cheap before the digital revolution, so I would think they'd be even cheaper now. Bigger names like Hasselblad and Mamiya are going cheaper every day. The Hasselblad 500 series cameras are legendary, and they are even building digital backs that will fit on them.
Rangefinders like the Fujis and Mamiyas are a little smaller than the SLRs. Old folding cameras are tiny for medium format. I carry a 6x6 folder that actually fits in my pocket.