I'd like to start off by saying congratulations for owning one of the greatest Macintosh computers ever made.
Definitely upgrade your CPUs as others have stated using the CPU compatibility list on this forum. Note that the 130W TDP chips are going to use more power even when the computer is idle so consider getting a pair of 95W X5675 instead of going for the top performing X5690 chips if power usage is a concern for you. Get an RX 580, you don't need to buy the Sapphire PULSE RX 580 I have an MSI one and it works just fine. Note that you do lose the boot screen with any RX 580 that you buy. You can also go higher and get an RX 590 or Vega 64 but the power requirements make these cards harder to install as you need to steal power from the SATA bus or do power supply mod to properly power these cards.