For starters, take a look at broker deals in the Marketplace for cars/SuVs that might fit your budget.
As others have stated, without much credit history you might have a hard time getting approved for a lease. As far as insurance, being a new driver is not going to be cheap. Hence, your $500/month budget might be unrealistic.
I’ve started my search with used cars, but the longer I search, the prices seem exorbitant and sometimes two year old cars with low mileage price match the new vehicles. Which is ridiculous.