Reboot, then hold down Alt key almost immediately. Wait while still holding it down. If you eventually get a screen asking you which disk to boot from, you have success. Otherwise you have your unfortunate answer.
Another trick may be to try installing Refind. I don't know if this ability got removed with that upgrade to a 'metal' card like the 580, but may be worth a try?
http://www.rodsbooks.com/refind/installing.html
One thing you
can do is buy a well used ATI 4870 or 5870 from ebay for $100 or even less. Even if it has a bad fan (they often get gunked up and sounds scratchy), you can just run both in parallel and use the 580 for linux, 4870 just to get access to the boot screen as the default OSX card.
You have to take care to find an REAL official Apple one. I bought one and it was aftermarket which won't do the trick for you. Go to Ebay and look for ones that have one DVI and one mini Displayport. If you see one with two DVI that's not an Apple one.
I just did a search and found a 4870 and 5870 for between $50-$60
That may do the trick.
For a nice zippy experience, i have been experimenting with Linux distros recently. For good stability, nice mac like interface try Elementary OS. Use 'Etcher' on mac to burn their ISO to a thumbdrive and you are off to the races. Elementary really is very stable, and has a nice experience. The 'Photos' app is a fork of Shotwell and is really quite a good alternative to Apple Photos. Elementary doesn't have global menus etc, but you will feel quite at home. Also very fast. Zorin also worth a look. Zorin has some nice UI options. These are both downstream from Ubuntu distros, but well supported. I tried Ubuntu (Budgie), and found stability and speed to be a big problem. Tried Fedora, Solus, but they lack application support.
If you do install, try installing Flatpak and Snap to get access to more apps.
I'm still on the fence moving to Linux myself. My big hold back is photography app support after growing a massive 20 year image catalog in Lightroom. I'm looking at just upgrading my Mac Pro 4,1 (which is now a 5,1 after putting in a 5870 two years back) to a Mojave capable machine by getting one of those ATI 580 cars to run alongside the 4870 so I can do Linux on a separate disk.
The move to ARM is annoying. I have successfully installed Elementary and Zorin on some old macs for the kids (for years now). Not being able to recycle these perfectly good old computers is quite annoying. Just like it is now quite annoying that I can't upgrade my $3000 Mac Pro that has perfectly adequate specs (8 2.2ghz cores, 12GB RAM).