First decide on a format. Then you have to beware that $500 on a medium format camera may mean one that will need a service pretty soon, ie another $100-200 just for a normal service. On the other hand, my experience with repairs is that they all pretty much cost the same nowadays.
For $500 you can easily get a very good condition one of those:
Mamiya RB67 ProS or ProSD (don't bother with the plain Pro)
Mamiya C330S (latest model)
Bronica SQAi/SQB
Bronica ETRSi (latest)
These are all great cameras, the SQB was my first medium format camera.
You could probably find a beat up Hasselblad 500C or 500CM but up to you to decide if you want to spring another $150 or so for a service. It would be easier to find a 500ELX body (they seem to go for less). These actually handle better (in my books at least) but make sure it takes AA batteries or get one of those 9V/2CRP adapters.
I would advise against getting an old Pentax 6x7 as that is now impossible to repair (I had one). If you can find a 67 though for $500 maybe that would be a good one. There's also the Mamiya 645 stuff which is great (the manual focus ones, not the AF ones obviously).
You can get some other stuff like folders or some Russian stuff but I would not consider them as a first "step up" camera.
My choice would be a Mamiya RB67 ProSD with a 90KL lens. That is a step up in everything, quality, wow factor when you look at the finder, WOWOHMYGOD factor when you get the negs/photos from the lab and obviously a massive step up in size and weight