Should i Upgrade my CPU or GPU first ?

Solution
In game performance the 6XXX series is fairly close to the 8XXX series, so up to a 1060 is the range you should look at. Sure, some games won't run as fast on that CPU, but you'll still get value since performance will be vastly improved from that 360 you have now.
The FX-6300 can handle a faster card than the R7-360 w/o major bottleneck. And the gfx card will make the biggest difference in gaming right now for you. Especially if you get one with at least 4GB of VRAM.

I don't know where in Europe you are buying, but 500 Euros should get you both a CPU and GPU upgrade.
 
For current games, both a somewhat lacking. I think you can handle a GTX1050 OK or a R460, but anything more than that you are likely going to need a better CPU. I have a GTX1060 with a FX8350 and it works pretty well, I run current games on ultra settings.