Used is definitely the way to go to keep the budget low.
On the AMD side, HD 7970's have been on the $100 or even lower for a good many years, which would mean you could probably find some R9 290's for $100 if you looked hard enough. Just think of R9 390's as rebadged R9 290's. Probably the slightly slower equivalent of a single GTX 970 on NVIDIA's side (which I don't recommend, personally, even though others would), which in turn is a slightly slower equivalent of the RX 480 on the AMD side.
In terms of your HD 6870, the R9 290 is at least 150% better overall than what you have now, and would be more than capable of running Diablo3 and Skyrim on Ultra at 1080P with even HD textures.