These are affordable on second hand market and are very suitable for upland game: Franchi 48AL 20ga 28ga, Ithaca 37 16ga 20ga, Remington 31 16ga 20ga, early 50s 870 16ga, 870 LW 20ga 28ga, Model 12 16ga. These are superior to anything in sxs you're likely to find for $500. If you must go with double for $500 or less look for Marlin 90 20ga with separated barrels.
If I needed upland gun I would save money and get me 16ga Browining Citori. Local shop has one NIB with choke tubes for under $1400. Why? Just because 16ga Browining O/U is kinda cool.