Definitely go with the Ryzen 1600 over the 1500x. It is not even close.
As for the 580, 4gb will be fine for 1080p. But if you are wanting to play at 1440p, the VRAM may become an issue. However, the 580 is not a 1440p card and you will have to dial back settings to get good fps. So if you are playing at 1440p, you will need a 1070 which is a lot higher.
I would get a 1060 6gb. As it tends to beat the 580 in most games. But if you have a free sync monitor, then you should get the 580.